RU/2: Форум. Общение пользователей и разработчиков OS/2 (eCS). : Ответить на сообщение

Имя:
e-mail:
FIDO:
Home page:
сохранить данные о вас

Тема:

> > Ага, давай, на чем ты там будешь писать - сравни время выполнения
> > 
> > for (i=0; N>i; i++) a[i]=new int;
> > и
> > for (i=0; N>i; i++) delete a[i];
> > 
> > где int *a[N];
> > а N - не менее 100000
> 
> Вот в жабе delete нету :-) А твой пример должен везде работать одинакого, разве что в виртуал паскакле будет по другому - он сам с кучей геморроется (imho).
>  
> > > > Я с большим удовольствием почитаю твой исходничек, который с такими строками работает.
> > 
> > Я кстати тоже. Подскажи, где почитать, чтобы узнать алгоритм, быстрый и безразличный к статистике как qsort и нетребовательный к размеру ОЗУ и времени выборки внешней памяти. 
> 
> Нуууу блин. Если рассмотреть алгоритм qsort-а, то он де факто строит сбалансированное дерево. Однако вместо хранения элементов в памяти он их, мммм, перестанавливает. Соответственно и памяти жрется мало. В случае больших массивов сразу напрашивается вариант строить дерево хеш функций. Это позволит избежать многократного перемещения элементов, повышая за счет этого производительность (ведь основное время тратится именно на выборку и перемещение). За счет построения дерева можно к тому же сократить время работы проги, так как сортировать весь массив не требуется. Причем значительно. Грубо говоря: требуется балансировка не всего дерева, а только одной его ветки. Соответственно и количество сравнений снижается в кубической прогрессии. (На самом деле не совсем конечно). Ну и т.д. Эти и другие более умные вещи можно почитать в книжке Кнутта (по моему так), выпущенной в каком то занюханном 60 году. Вот-с. 
> Что касается сравнения больших строк, например в 500мег (как тут ехидно заметил товарисч Кулешов), то для этого существует другие алгоритмы - например можно использовать модифицированный(на >,<,=) алгоритм Кнутта-Морриса-Братта, для сравнения двух строк. Есстественно его придется написать на asm-е для повышения производительности. Вот конкретно в этом 
> месте жаба конкретно и отсосет.
> 
> > > Ты отказался сформулировать тестовую задачу, это сделал за тебя я.
> > 
> > Это очень хорошо, что ты её уже сформулировал, только вроде как никто кроме тебя её ещё не понял. 
> 
> Я её уже повторно сформулировал. Даже товарисч Кулешов её понял :-)
> 
> >А ещё ты не сформулировал, на каких примерах сверять будешь.
> 
> Нормально написанный софт должен нормально работать на любых примерах.
>

__, _, __, _,_ _, _ \|_ / \ \|_) \| \| \|\/\| \| \ / \| \ \| \| \| \| ~ ~ ~ ~ `~' ~ ~