Разработка поисковой системы

а также заготовки для микроволновки в обойме есть %) Со всем уважением к присутствующим, тема остается неизменной. Спасибо.

проблемы есть такие:

1. В данном контексте человек, который не умеет сортировать данные "вручную", никак не может быть разработчиком.

2. В сортировке STL еще недавно была серьезная ошибка - в отличие от стандартной qsort она не была гладкой. Т. е. если в неотсортированном массиве есть два элемента с одинаковыми ключами, после сортировки они могли поменять свой порядок.

3. Я еще не видел проектов, использующих STL, для которых выполнялась бы на произвольной платформе последовательность

> cvs get project

> cd project

> make

А что касается сортировки вообще... Я, составляя тестовые задания для программеров в Рамблере и в свое время в Мете, просил отсортировать некоторое количество гигабайт строк. На машине с 512 мегами памяти. И заметил, что сортировка слиянием - это какая-то terra incognita :)

В терминах Кнута, соортировка не меняющая порядка элементов с одинаковыми ключами называется устойчивой. Метод быстрой сортировки (qsort) по жизни не является устойчивым.

🙄

Я скажу больше, в GNU реализации qsort и в реализации от BSD существуют существенные отличия в скорости в пользу Беркли - проверено электроникой :)

Господа, STLая сортировка очень даже неплоха. Вряд ли кто-нибудь напишет версию, которая будет работать быстрее чем на 10-20%. Опять-таки, говоря про STL неплохо было бы называть версию и конкретную реализацию STL. Так, например, в некоторых версиях (старых) GNU Stl для GCC 2.95 sort "подвисал" на больших объемах. Зато stable_sort работал нормально. Возвращаясь к вопросу стабильной сортировки, а разве stable_sort не стандартизированная фича?

И еще, кстати, мне почему-то кажется, что в современной поисковой машине скорость сортировки в памяти (в смысле 20-30% вариаций) не играет почти никакую роль. Потому, как если происходит слияние временных индексов, то там как минимум 90% времени сжирается работой с диском. А если происходит поиск, то он работает, как правило, с отсортированными или частично отсортированными списками записей.

При разработке программного комплекса, системы не "на день", использование STL вообще категорически противопоказано!

А если система еще и должна быть портируемой, то противопоказано вдвойне.

И причина в том, что STL, что бы ни говорили, катастрофически нестандартная штука, и разные версии его, например, 4 и 5, можно вообще считать абсолютно разными библиотеками.

Поясните, плз, что значит разные версии STL? Все-таки, я это отношу больше к реализациям. Вы, конечно, правы, что разные реализации не вполне совместимы. Но если не использовать STL, то нужно использовать какой-то его аналог. А аналоги, я сам лично видел, кривее медленнее и хуже адаптированы к разным платформам. Возьмите, например, STLPort. И будем Вам счастье, а лучше Вы все равно (в общем и целом по интегральной оценке) не напишите. В частности там одна из самых "быстрых" реализаций строки (для строк размером до 100-200Кб точно). По-крайней мере, она сильно быстрее GNU string под FreeBSD и Linux.

Keva, с днем рождения :)

/ru/forum/31063

... в мультитредовом окружении ...

В однотредовом сильно медленнее.

И потом: все зависит от теста, я могу написать такой тест, что все будет ровно наоборот.

Иными словами: для разных задач разные string-и могут оказаться лучше или хуже.

Собственно речь шла больше про самописные vs стандартные, посему сразу хочу напомнить про один самописный класс, который был медленнее GNU и STLPort. 😂 😂 А еще про некий частичносамописный класс hash_map, который быстрее стандартного в два раза (а на самом деле не быстрее).

А теперь по поводу сравнения более быстрых готовых:

Илья, я знаю, что ты ничего не тестировал. И задачу такую, на которой GNU быстрее STLPort, придумать очень трудно, потому что

а) STLPort был до 2 раз быстрее в именно в однотредном режиме. В том числе на вполне реальных достаточно сложных приложениях, одно из которых: веб-сервер.

б) "Искусственные" тесты как раз тестировали основные операции работы со строкой: вставку, удаление, увеличение размера, поиск. Единственная обнаруженная операция, которая работает быстрее - создание пустой строки (на 10-20%), но она не очень частая. Поэтому единственный способ написать такой тест, про который ты говоришь, создать миллиард пустых строк или написать что-то, что предполагает refcounting при реализации строки, например:

string getStr(int k = 0) {

if (k<1000) return getStr(k+1);

return string("test string");

};

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

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