VPF::Самый быстрый способ сортировки строк

zim22

Дата 1.7.2009, 07:16 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Riddik @ 30.6.2009, 22:49

)

Далее по порядку, каждое слово сравнивается со всеми mind[i].name

нет нужды это делать.
достаточно использовать алгоритм std::set_intersection (т.е. из двух множеств создать третье, которое содержит элементы, которые одновременно есть и в первом и во втором множестве).
каждое множество - это набор слов-ассоциаций для объекта. т.к. множеств может быть больше двух

Цитата

whale penguin piano jackboot train

то все множества не нужно стравнивать. т.к. если после первой операции set_intersection новое множство будет пустое (ф-яe mpty()), то нет смысла продолжать дальнейший поиск (общих слов не будет, т.к. у "двух множество" уже не было). соответственно break делать из цикла.
думаю, должно работать довольно быстро.

Цитата(Riddik @ 30.6.2009, 17:13

)

Какие ещё способы, более скоростные?

сортировать(перемещать в памяти) не строки, а массив указателей на них. с помощью qsort.

Это сообщение отредактировал(а) zim22 - 1.7.2009, 07:29

--------------------

C++ FAQ Lite

Riddik

Дата 1.7.2009, 11:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Спасибо.

kamre

Дата 1.7.2009, 11:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 330
Регистрация: 24.3.2006

Репутация: 2
Всего: 13

В общем я тут на stl намудрил и оно даже прошло (0.89 / 13 341 KB):

Код


#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <iostream>

using namespace std;

typedef set<string> names_t;
typedef map<string, names_t> items_t;
typedef vector<names_t> queries_t;

void readItems(istream & in, items_t & map) {
  int itemsNumber;
  in >> itemsNumber;
  string dummy;
  getline(in, dummy);
  while (itemsNumber--) {
    string line;
    getline(in, line);
    istringstream iss(line);
    string item;
    iss >> item;
    item.erase(item.length() - 1);
    names_t associations;
    while (!iss.eof()) {
      string association;
      iss >> association;
      associations.insert(association);
    }
    map[item] = associations;
  }
}

void readQuires(istream & in, queries_t & quires) {
  int queriesNumber;
  in >> queriesNumber;
  string dummy;
  getline(in, dummy);
  while (queriesNumber--) {
    string line;
    getline(in, line);
    istringstream iss(line);
    names_t names;
    while (!iss.eof()) {
      string item;
      iss >> item;
      names.insert(item);
    }
    quires.push_back(names);
  }
}

void process(const items_t & items, const queries_t & queries) {
  queries_t::const_iterator query;
  for (query = queries.begin(); query != queries.end(); ++query) {
    names_t::const_iterator item = query->begin();
    const names_t & associations = items.find(*item)->second;
    vector<string> common;
    copy(associations.begin(), associations.end(), inserter(common, common.begin()));
    while (++item != query->end()) {
      const names_t & associations = items.find(*item)->second;
      vector<string>::iterator end;
      end = set_intersection(common.begin(), common.end(), 
                             associations.begin(), associations.end(), 
                             common.begin());
      if (end != common.end())
        common.erase(end, common.end());
      if (common.empty())
        break;
    }
    if (common.empty()) {
      cout << "No solution.\n";
    } else {
      vector<string>::const_iterator iter = common.begin();
      cout << *iter++;
      while (iter != common.end()) {
        cout << ' ' << *iter++;
      }
      cout << '\n';
    }
  }
}

int main() {
#ifdef ONLINE_JUDGE
  istream & input = cin;
#else
  istream & input = ifstream("input.txt");
#endif
  items_t items;
  readItems(input, items);
  queries_t queries;
  readQuires(input, queries);
  process(items, queries);
  return 0;
}

Похоже что очень не оптимально получилось у меня... Даже медленее простой Java версии с ее HashMap и HashSet, хотя памяти чуть поменьше используется.
Как теперь этот код можно ускорить, оставаясь в рамках stl?

zim22

Дата 1.7.2009, 11:54 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(kamre @ 1.7.2009, 11:43

)

В общем я тут на stl намудрил

намудрили так намудрили smile

я вечером выложу свою версию кода. сейчас нет времени писать.

Цитата(kamre @ 1.7.2009, 11:43

)

оно даже прошло (0.89 / 13 341 KB):

где вы взяли тестовый файл?

Это сообщение отредактировал(а) zim22 - 1.7.2009, 11:55

--------------------

C++ FAQ Lite

kamre

Дата 1.7.2009, 12:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 330
Регистрация: 24.3.2006

Репутация: 2
Всего: 13

Цитата(zim22 @ 1.7.2009, 11:54)

намудрили так намудрили smile

Ну я старался, чтобы было похоже на мою Java версию smile

Цитата(zim22 @ 1.7.2009, 11:54)

я вечером выложу свою версию кода. сейчас нет времени писать.

Ждем-с, интересно сколько даст более правильное использование stl smile

Цитата(zim22 @ 1.7.2009, 11:54)

Цитата(kamre @ 1.7.2009, 11:43

)

оно даже прошло (0.89 / 13 341 KB):

где вы взяли тестовый файл?

Нигде не брал, это результаты с http://acm.timus.ru/status.aspx?space=1&am...status=accepted

Riddik

Дата 1.7.2009, 13:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Как же там умудряются за 0.046 с. делать? На С++.
В моей версии памяти около 300 кб, но в тайм-лимит не укладывается. Причём, даже не узнать, насколько.

Это сообщение отредактировал(а) Riddik - 1.7.2009, 13:05

zim22

Дата 1.7.2009, 13:12 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Riddik @ 1.7.2009, 13:01

)

Причём, даже не узнать, насколько.

сгенерируйте сами файл из 1000 записей. и время посчитайте smile

--------------------

C++ FAQ Lite

kamre

Дата 1.7.2009, 13:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 330
Регистрация: 24.3.2006

Репутация: 2
Всего: 13

Цитата(Riddik @ 1.7.2009, 13:01)

Как же там умудряются за 0.046 с. делать?

Ну там же в задачке есть специальные ограничения на количество объектов, количество запросов и максимально возможную длину строки на входе. Так что вполне можно заоптимизировать под это дело. Впрочем, подождем решения от zim22, наверняка при правильном использовании stl можно раз в десять ускорить мой вариант smile

Riddik

Дата 1.7.2009, 15:40 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Немного в сторону, чтоб не создавать отдельную тему.

Даже с такой простой задачей у меня траблы. Укажите, пожалуйста, что не так делаю.
Задача:

Цитата

You are given the whole numbers N, M and Y. Write a program that will find all whole numbers X in the interval [0, M−1] such that XN mod M = Y. (X в степени N)
Исходные данные
The input contains a single line with N, M and Y (0 < N < 999, 1 < M < 999, 0 < Y < 99) separated with one space.
Результат
Output all numbers X separated with space on one line. The numbers must be written in ascending order. If no such numbers exist then output −1.
Пример
исходные данные ========================== результат
2 6 4 =================================== ===== 2 4

Мой код:

Код


#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    unsigned long i, N, M, Y, X;
    bool bFound=false;
    cin>>N>>M>>Y;
    if(Y==1) {cout<<1; bFound=true;}
    if(Y==0) {cout<<0; bFound=true;}
    if(!bFound)
    {
        for(i=2; i<M; i++) 
        {
            X=(unsigned long)powl((long double)i, (long double)N);
            if(X%M==Y) {cout<<i<<" "; if(!bFound) bFound=true;}
        }
    }
    if(!bFound) cout<<-1;
    return 0;
}

Пишет, что ответ не верный.

Ссылка на задачу

Это сообщение отредактировал(а) Riddik - 1.7.2009, 19:16

zim22

Дата 1.7.2009, 16:15 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Riddik @ 1.7.2009, 15:40

)

Немного в сторону, чтоб не создавать отдельную тему.

создавайте, не стесняйтесь.

--------------------

C++ FAQ Lite

Riddik

Дата 1.7.2009, 17:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Так и сделал smile

zim22

Дата 1.7.2009, 21:50 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(kamre @ 1.7.2009, 13:17

)

подождем решения от zim22, наверняка при правильном использовании stl можно раз в десять ускорить мой вариант

я отстой

. тест не пройден.

Цитата

Judgement result: Time limit exceeded

http://acm.timus.ru/status.aspx?space=1&am...p;status=failed

вот мой код smile

Код


#include <algorithm>
#include <iterator>

#include <set>
#include <map>
#include <string>
#include <vector>

#include <iostream>
#include <fstream>
#include <sstream>

using namespace std;


void fill_map(std::map<std::string, std::set<std::string> > &map_to_fill,
              std::istream &input) {

  int object_cnt = 0;  
  input >> object_cnt;
  input.ignore();

  std::string line;            // одна строка текста
  std::string object_name;     // имя сущности
  std::string assoc_name;      // строка, содержащая список ассоциаций

  std::istringstream is;

  while (object_cnt-- > 0) {
    getline(input, object_name, ':');  // получить имя сущности
    getline(input, line); // получить список ассоциаций в виде строки
    
    is.str(line); // связать строку с потоком
    while (is >> assoc_name) {
      // создать запись в ассоц.массиве (ключ -> множество ассоциаций)
      (map_to_fill[object_name]).insert(assoc_name);
    }
    is.clear(); // очистить поток    
  }    
}


void fill_query_table(std::vector<std::vector<std::string> >  &queries, 
                      std::istream &input) {
    
  std::istringstream is;
  std::string assoc_name;
  std::string line;

  for (size_t idx = 0; idx != queries.size(); idx++) {
    getline(input, line);
    is.str(line);
    while (is >> assoc_name) {
      queries[idx].push_back(assoc_name);
    }
    is.clear();      
  }    
}

void find_intersection_and_print(
    std::map<std::string, std::set<std::string> > &associative_words,
    std::vector<std::vector<std::string> > &queries
    ) {  
  
  std::set<std::string> result_set;
  std::set<std::string> accumul_result;
  bool mismatch_flag = false;

  for (size_t idx = 0; idx != queries.size(); idx++) {

    mismatch_flag = false;
    result_set.clear();
    result_set = associative_words[*queries[idx].begin()];

    for (std::vector<std::string>::iterator name_it = queries[idx].begin();
         name_it != queries[idx].end() - 1;
         ++name_it) {           
           
           std::set_intersection(
             result_set.begin(),
             result_set.end(),
             associative_words[*(name_it + 1)].begin(),
             associative_words[*(name_it + 1)].end(),
             inserter(accumul_result, accumul_result.begin())
           );
           if (accumul_result.empty()) {
             mismatch_flag = true;
             break;
           }
           else {
             result_set.swap(accumul_result);
             accumul_result.clear();
             continue;
           }                        
    }
    if (mismatch_flag == true)
      std::cout << "No solution.\n";
    else {
      std::copy(result_set.begin(), 
      result_set.end(), 
      std::ostream_iterator<std::string>(std::cout, " "));
      std::cout << std::endl;
    }
  }
}
int GetQueryNumRecords(std::istream &input) {
  int query_cnt = 0;
  input >> query_cnt; // считать кол-во строк запроса
  input.ignore();     // пропустить символ-разделитель из потока ввода
  return query_cnt;
}

int main(int argc, char **argv) {
#  ifdef ONLINE_JUDGE
    istream &input = cin;
#  else
   istream &input = ifstream("input.txt");
#  endif        

  // заполнить карту associative_words
  std::map<std::string, std::set<std::string> > associative_words;
  fill_map(associative_words, input);
  
  // создать массив со значениями для поиска    
  int query_number = GetQueryNumRecords(input);
  std::vector<std::vector<std::string> > queries(query_number, std::vector<std::string>());
  fill_query_table(queries, input);

  // найдём пересечения множеств (сам алгоритм) и выведем на экран результаты
  find_intersection_and_print(associative_words, queries);    
  
  return 0;
}

Это сообщение отредактировал(а) zim22 - 1.7.2009, 21:50

--------------------

C++ FAQ Lite

Riddik

Дата 1.7.2009, 22:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Да ладно, уверенн, если б Вы этим занялись капитально, а не вечером после работы, было бы всё нормально.

Только по коду не пойму.
Если объявляете пространство имён std видимым, зачем используете оператор разрешения области видимости к каждому идентификатору из std?

А вообще по задаче, там среди лучших решений есть за четыре сотых секунды, причём на С++. Есть быстрые решения на чистом С, но самое быстрое на С++. Интересно, использовали ли ассемблер... Что ж там за код? smile

Это сообщение отредактировал(а) Riddik - 1.7.2009, 22:37

zim22

Дата 1.7.2009, 22:43 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Riddik @ 1.7.2009, 22:32

)

Если объявляете пространство имён std видимым, зачем используете оператор разрешения области видимости к каждому идентификатору из std?

я сначала без

Код


using namespace std

весь код написал, но онлайн-компилятор начал ругаться, что функция getline не определена. мне лень было std:: приписать к ней smile

***
я хотел добиться более быстрого выполнения кода за счёт того, что объявлял переменные вне циклов (т.е. чтобы они не создавались каждый раз).
но я думаю основной тормоз был в фунции set_intersection, а именно то, что я выбрал тип set. думаю с векторами быстрее было бы.

Цитата(Riddik @ 1.7.2009, 22:32

)

А вообще по задаче, там среди лучших решений есть за четыре сотых секунды, причём на С++.

может они алгоритм какой-то использовали или структуру данных хитрую.

Это сообщение отредактировал(а) zim22 - 1.7.2009, 22:47

--------------------

C++ FAQ Lite

Riddik

Дата 1.7.2009, 22:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Забьёте или будете ещё решать?

Добавлено через 5 минут и 12 секунд
У них там Интелловский компилятор, 7ой вроде бы.
Дома бесполезно мерять время - у них будет другое, что у них за система (сервак) - не известно.

Так вот, их компилятор ругался на ф-ию сортировки, я сначала в вектор записывал результат, потом сортировал:

Код


qsort(rezalt.begin(), sizeof(string), rezalt.size(), strcmp);

Но с этой ф-ией не компилится, ругается, что не может преобразовать первый параметр в void*.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »