В общем упор на скорость доступа к элементам+ чтобы не было заморочек с выделением памяти.
std::list не подходит ---линейный доступ к элементам. std::vector --хз, не в курсе про скорость доступа.
Еще упор на компактность размещения в памяти. К примеру std::list занимает в раме 70 метров с 250000 строковых элементов, каждый по 34 символа.
Примечание:
1 - да, однократная сортировка
2 - изменяться ничего не будет---однократное добавление.
3 - нет
4 - не принципиально.
------------
В общем алгоритм таков - программулина хавает текстовый файлик, подгружает его в контейнер, разделяя элементы символом переноста строки, далее сортировка, а уже потом будет происходить непрерывный поиск каждый раз разной строки несколькими потоками(дабы не создавать узкое место в виде очереди при блокировке--для каждого потока будет отдельная копия контейнера).
Упор на моментальный поиск тоже важен.
Возможно буду хранить ни строки, а делать над ними некое преобразование и полученную последовательность байт уже буду хранить в контейнере и осуществлять поиск в них.
Может есть какие-либо коробочные решения бинарных деревьев?
Еще мне важна кроссплатформенность в пределах --форточки+никсы, чтобы я мог качнуть сорец на машину с дебианом и там просто собрать с помощью g++, ну ессно предварительно воткнув зависимости, если такие появятся%)
Примечание:
Заюзал std::vector
Find SfSfeTtYyUuOSaAfSfSfeTtYyUuOSaAfaa
=index: 136586, value: SfSfeTtYyUuOSaAfSfSfeTtYyUuOSaAfaa
Time: 0.000000 sec
Bench: 100000 IndexOf(rand) = Time: 0.855000 sec
List size: 264146
Поиск бинарный--тупо переписал функцию поиска из делфей TStringList.
Код
https://github.com/r3l0c/cppstringlist/blob/master/stringlist.h
clock_t t=clock();
StringList strings;
strings.LoadFromFile("data.txt");
string fnd;
fnd="SfSfeTtYyUuOSaAfSfSfeTtYyUuOSaAfaa";
t=clock();
int spos=strings.IndexOf(fnd);
t=clock()-t;
printf("\n\nFind %s = index: %d, value: %s\n Time: %lf\n",fnd.c_str(),spos,strings[spos].c_str(),double(t)/CLOCKS_PER_SEC);
//+++++++++++++++++++++++++++++++
printf("Bench: 100000 IndexOf()");
srand (time(NULL));
int ls=strings.List.size();
t=clock();
for (int i=0;i<100000;++i){
int spos=strings.IndexOf(strings.List[rand() % ls]);
}
t=clock()-t;
printf("\nTime: %lf\n",double(t)/CLOCKS_PER_SEC);
Примечание:
Ок. Заюзаю мап, спасибо)
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.