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

baldina

Дата 1.7.2009, 23:44 (ссылка)

(голосов:3)

Загрузка ...

Эксперт

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

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

Цитата

там умудряются за 0.046 с. делать

Цитата

У них там Интелловский компилятор, 7ой вроде бы.

компилятор крутой, но в 10 раз быстрее даже он не сделает.
почему все пытаются сравнивать строки? их сравнивать надо один раз, в момент размещения. и каждой строке присваивать числовой индекс. каждому объекту соответствует набор числовых индексов. если их хранить отсортированными, можно использовать двоичный поиск, не используя деревьев. плюс выигрыш в операции сравнения.

навскидку: не может ли быть полезен boost::multimap?

kamre

Дата 2.7.2009, 09:18 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(zim22 @ 1.7.2009, 22:43)

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

Ну это вроде не принципиальная оптимизация...

Цитата(zim22 @ 1.7.2009, 22:43)

но я думаю основной тормоз был в фунции set_intersection, а именно то, что я выбрал тип set. думаю с векторами быстрее было бы.

Я тоже сначала хотел в set результат складывать, но потом заметил, что там любую последовательность можно использовать. Тем более там элементы всегда в строго возрастающем порядке добавляются, так что похоже при добавлении в set там часто дерево перестраивается.

Еще вполне возможно в запросе наделать дубликатов и тогда set для хранения имен там лучше, т.к. не нужно будет искать пересечения заведомо одинаковых множеств.

Цитата(zim22 @ 1.7.2009, 22:43)

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

Вообще там входных данных всего не более 512Kb ~ 1000*250 (ассоциации) + 1000*250 (запросы). При чем для самих ассоциаций можно сделать один список, отсортировать его и далее всегда уже оперировать только с номерами в этом списке. По идее запросы на пересечение множеств с числами будут гораздо быстрее работать. Еще у меня есть подозрее на то, что на перекладывание строк из контейнера в контейнер может тратиться заметное время на копирование.

P.S. пока Java вариант с его immutable строками и hash-based контейнерами быстрее аналогичного варианта на stl...

Это сообщение отредактировал(а) kamre - 2.7.2009, 13:23

Riddik

Дата 2.7.2009, 10:28 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(kamre @ 2.7.2009, 09:18

)

P.S. пока Java вариант с его immutable строками и hash-based контейнерами быстрее аналогичного варианта на stl...

Ваш результат на джаве попал в общую сотку лучших. smile

А вообще вышла поразительная ситуация. Решение на Java быстрее и компактнее (код заметно меньше), чем решение на С++. Что делается...! smile

Это сообщение отредактировал(а) Riddik - 2.7.2009, 10:33

kamre

Дата 2.7.2009, 11:16 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Riddik @ 2.7.2009, 10:28)

А вообще вышла поразительная ситуация. Решение на Java быстрее и компактнее (код заметно меньше), чем решение на С++.

Я там выше не весь код для Java приводил, а только метод для выполнения запросов. Так что там кода примерно столько же в итоге будет.

Цитата(Riddik @ 2.7.2009, 10:28)

Что делается...! smile

В Java другие контейнеры используются, алгоритмически более эффективные. Кроме того строки immutable и никогда не копируются, т.к. везде передаются по ссылке. Так что можно еще выжать из stl, тем более что самые быстрые варианты еще в раз в 10-15 быстрее чем мой вариант на Java.

mes

Дата 2.7.2009, 12:00 (ссылка)

(голосов:1)

Загрузка ...

любитель

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

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

что то ситуация с этой задачей меня заинтересовала, будет время - попробую набросать решение.

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

http://opendots.net

kamre

Дата 2.7.2009, 13:11 (ссылка)

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

Загрузка ...

Опытный

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

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

Вот немного обновленная полная версия решения на Java (0.656 / 11 170 KB):

Код

import java.io.*;
import java.util.*;

public class Timus1700 {
  private static BufferedReader in;
  private static PrintWriter out;

  private Map<String, Set<String>> itemAssociations;

  private void readAssociations() throws NumberFormatException, IOException {
    int itemsCount = Integer.parseInt(in.readLine());
    itemAssociations = new HashMap<String, Set<String>>(itemsCount);
    while (itemsCount-- > 0) {
      // read string and split it to item's name and all associations
      String[] parts = in.readLine().split(": ");
      // parse item's associations and put them to corresponding HashSet
      Set<String> associations = new HashSet<String>();
      for (String word : parts[1].split(" ")) {
        associations.add(word);
      }
      itemAssociations.put(parts[0], associations);
    }
  }

  private void processQueries() throws NumberFormatException, IOException {
    int queriesCount = Integer.parseInt(in.readLine());
    Set<String> query = new HashSet<String>();
    Set<String> common = new HashSet<String>();
    while (queriesCount-- > 0) {
      // read next query
      query.clear();
      for (String name : in.readLine().split(" ")) {
        query.add(name);
      }
      // initialize common with copy of associations of first name in the query
      Iterator<String> iter = query.iterator();
      common.clear();
      common.addAll(itemAssociations.get(iter.next()));
      // intersect common with associations of other items in the query
      while (iter.hasNext()) {
        common.retainAll(itemAssociations.get(iter.next()));
        // check if intersection is already empty
        if (common.isEmpty())
          break;
      }
      if (common.isEmpty()) {
        out.println("No solution.");
      } else {
        // common is HashSet, so we need to sort associations from common
        String[] commonArray = common.toArray(new String[common.size()]);
        Arrays.sort(commonArray);
        // print all common associations
        for (int i = 0; i < commonArray.length; i++) {
          if (i > 0)
            out.print(' ');
          out.print(commonArray[i]);
        }
        out.println();
      }
    }
  }

  public static void main(String[] args) throws Exception {
    in = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(new OutputStreamWriter(System.out));
    Timus1700 problem = new Timus1700();
    problem.readAssociations();
    problem.processQueries();
    out.flush();
  }
}

Если заменить все HashMap/HashSet на TreeMap/TreeSet, которые алгоритмически соответствуют std::map/std::set, и убрать лишнюю сортировку перед выводом результатов то работает медленнее, но все равно проходит: (1.296 / 11 454 KB).

Riddik

Дата 2.7.2009, 13:16 (ссылка)

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

Загрузка ...

Опытный

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

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

kamre, респект smile

По какой причине может попасть в бесконечный цикл на последней строке?

Если установить число итераций меньше на единицу, чем нужно, то пробегает быстро, но ответ, соответсвенно неверный, если задать верное число итераций, то сразу превышается тайм-лимит. Не может же последняя итерация длиться больше, чем все итерации до неё вместе взятые?

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

kamre

Дата 2.7.2009, 13:29 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Riddik @ 2.7.2009, 13:16)

Если поставить, чтобы итераций было меньше на единицу, чем нужно, то пробегает быстро, то ответ, соответсвенно неверный, если сколько надо, то сразу превышает тайм-лимит. Не может же последняя итерация длиться больше, чем все итерации до ней вместе взятые?

Там же запускается набор тестов, и как только получается неверный ответ - сразу же заканчивается тестирование. Соответственно получается, что на первом же тесте заваливается программа, это очень быстро происходит. А последние тесты скорее всего как раз на timelimit, поэтому как только до них дело доходит программа прерывается снаружи и в табличке видно номер теста, на котором это произошло. Т.е. чем больше номер теста, на котором ошибка, тем больше тестов завершилось вовремя и правильно.

Riddik

Дата 2.7.2009, 13:34 (ссылка)

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

Загрузка ...

Опытный

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

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

Так и есть, я не обратил внимание.

Добавлено @ 13:41
m не может быть больше 1000, если ограничить число итераций в 999, то доходит до 9-го теста, в лимит времени влезает. Если оставить без ограничений, то доходит до 13-го теста.

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

kamre

Дата 2.7.2009, 15:01 (ссылка)

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

Загрузка ...

Опытный

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

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

Вот еще свое решение на C++ немного привел в порядок, глядя на код zim22:

Код

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

#include <algorithm>
#include <iterator>

#include <sstream>
#include <iostream>

using namespace std;

void readAssociations(map<string, set<string> > & item_associations) {
  int items_count;
  cin >> items_count;
  cin.ignore();

  string line;
  string name;
  string association;
  istringstream iss;

  while (items_count--) {
    getline(cin, name, ':');
    getline(cin, line);
    iss.str(line);
    set<string> & associations = item_associations[name];
    while (iss >> association)
      associations.insert(association);
    iss.clear();
  }
}

void processQuery(const set<string> & query, const map<string, set<string> > & item_associations) {
  set<string>::const_iterator name_it = query.begin();
  const set<string> & associations = item_associations.find(*name_it)->second;

  vector<string> common;
  copy(associations.begin(), associations.end(), inserter(common, common.begin()));

  while (++name_it != query.end()) {
    const set<string> & associations = item_associations.find(*name_it)->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 {
    copy(common.begin(), common.end(), ostream_iterator<string> (cout, " "));
    cout << '\n';
  }
}

void processQueries(const map<string, set<string> > & item_associations) {
  int queries_count;
  cin >> queries_count;
  cin.ignore();

  string line;
  string name;
  istringstream iss;
  set<string> query;

  while (queries_count--) {
    query.clear();
    getline(cin, line);
    iss.str(line);
    while (iss >> name)
      query.insert(name);
    iss.clear();
    processQuery(query, item_associations);
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "rt", stdin);
#endif  
  map<string, set<string> > item_associations;
  readAssociations(item_associations);
  processQueries(item_associations);
  return 0;
}

Даже побыстрее чем Java вариант: (0.64 / 6 749 KB). Действительно вынос переменных из циклов помог немного времени отыграть. И похоже, что более быстрые решения используют другие алгоритмы/структуры данных.

Riddik

Дата 2.7.2009, 15:10 (ссылка)

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

Загрузка ...

Опытный

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

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

Вопрос: как правильно передать адрес первого элемента в list функции qsort()?

Так

Код


qsort(rezalt.begin(), sizeof(string*), rezalt.size(), srav);

компилятор ругается, что не может конвертировать первый параметр в void*.
rezalt - это list, который хранит string*.

Это сообщение отредактировал(а) Riddik - 2.7.2009, 15:10

mes

Дата 2.7.2009, 15:25 (ссылка)

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

Загрузка ...

любитель

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

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

Цитата(Riddik @ 2.7.2009, 14:10

)

rezalt - это list, который хранит string*.

никак.

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

http://opendots.net

Riddik

Дата 2.7.2009, 15:27 (ссылка)

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

Загрузка ...

Опытный

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

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

И что делать?

zim22

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

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

Загрузка ...

depict1

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

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

Цитата(Riddik @ 2.7.2009, 15:27

)

И что делать?

ничего.
ипользуйте std::sort

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

C++ FAQ Lite

Riddik

Дата 2.7.2009, 17:21 (ссылка)

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

Загрузка ...

Опытный

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

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

Пока без std::sort нужно проверить.
Скажите, как правильно передать параметры ф-ии qsort в этом случае

Код


qsort(pstr[0], sizeof(string*), cwr, srav);

где

pstr[0] это string *pstr[N];
cwr это short, содержащий число указателей на string, которое нужно отсортировать.
srav() - самопальная ф-ия сравнения.

При обращении к ф-ии возникает критическая ошибка.

Это сообщение отредактировал(а) Riddik - 2.7.2009, 17:26

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