Нужен быстрый алгоритм отсортировать такую большую базу мыл - удалить дубликаты, может знает кто как это лучше сделать?

| Сообщение посчитали полезным:

А моё мыло там есть?

| Сообщение посчитали полезным:

Я откуда знаю Если хочешь добавлю

| Сообщение посчитали полезным:

Я убью тебя, лодчник.
А быстро. Это как ты понимаешь. За сколько у тебя это сейчас сортируется?

| Сообщение посчитали полезным:

Еще не сортировал, вот и спрашиваю как лучше, чтобы сэкономить пару суток

| Сообщение посчитали полезным:

Вообще нового тут вроде ничего не изобрели. Пузырьковая, пирамидальная да их там дохрена. В любом учебнике расписано.
А может чего Самогонщик подскажет. Он человек учёный.

| Сообщение посчитали полезным:

Вот нашёл у себя. Приложение к учебнику по D. Гл.9

| Сообщение посчитали полезным:

Блин ограничение на 200к

6038_Delphi_alg.001.zip

| Сообщение посчитали полезным:

2

c66e_Delphi_alg.002.zip

| Сообщение посчитали полезным:

3

da12_Delphi_alg.003.zip

| Сообщение посчитали полезным:

4

c033_Delphi_alg.004.zip

| Сообщение посчитали полезным:

5

ca53_Delphi_alg.005.zip

| Сообщение посчитали полезным:

6

3b6b_Delphi_alg.006.zip

| Сообщение посчитали полезным:

7

a9e8_Delphi_alg.crc.zip

| Сообщение посчитали полезным:

Переименуй в Delphi_alg.00x и собери.
Ща проверил. Массив из 100 000 10-значных алиментов сортирует за 12 сек (у кого круче комп ) Далее время растёт угрожающе

| Сообщение посчитали полезным:

TStringList.sorted:=true + dupIgnore - довольно быстро - 3-4 мега за секунды.

| Сообщение посчитали полезным:

Можно почитать третий томик Искусство програмирования от Д.Кнута...
а если именно сортировать для удаления дубликатов - то создать, например, хэштаблицу мыл(привести почтовые адреса для начала к одному регистру), отсортировать хэши(несколько проще,чем строки) и уже в такой отсортированной таблице шустрым двоичным(или интерполяционным) поиском искать многократные вхождения

| Сообщение посчитали полезным:

Вообще каждая сортировка себя ведет по разному поэтому лучшего алгоритма нет.
Но себя очень хорошо на практике показывают Универсальная быстрая (quicksort) и шейкер-сортировка.
В институте мы их стук 20 изучали, я чуть не опух
Обычно при выборе сортировки для большого количества данных, выделяют 3 типа данных:
1) хорошо упорядоченные
2) не очень упорядоченные
3) не упорядоченные
Ну и соответственно выбирают соответствующую сортировку.

-----
Никто не знает столько, сколько не знаю я

| Сообщение посчитали полезным:

Satanael
Во-во. Там исходниках они есть.

| Сообщение посчитали полезным:

Satanael пишет:
очень хорошо на практике показывают Универсальная быстрая (quicksort) и шейкер-сортировка.
шейкер, имхо, ничем не лучше пузырька.
и не понимаю, как сортировка со сложностью n**2 может показывать себя на уровне наиболее быстрого из фундаментальных сортировок квиксорта, с его средней сложностью n*(log2 n).

в данном случае лучше всего использовать merge sort, тем более замечательно распараллеливается.
делишь всю последовательность строк на k подпоследотельностей, сортируешь их любой сортировкой, потом сливаешь в одну.
я б сортировал пирамидальной. во-первых - точно можно посчитать время сортировки, во-вторых - ну не люблю я квиксорт

| Сообщение посчитали полезным:

NG
я б сортировал пирамидальной. во-первых - точно можно посчитать время сортировки, во-вторых - ну не люблю я квиксорт
----------------------------
Не пирамидальная фегня, Квиксорт форева.
Сделаю тест (если время будет) для этих двух сортировок, посмотрим какая быстрее окажется.
Квиксорт форева!!!!
Пирамидальная, хех, тыб ещё про метод простыми вставками вспомнил

-----
Никто не знает столько, сколько не знаю я

| Сообщение посчитали полезным:

Satanael пишет:
Не пирамидальная фегня, Квиксорт форева.
Сделаю тест (если время будет) для этих двух сортировок, посмотрим какая быстрее окажется.
Квиксорт форева!!!!
Пирамидальная, хех, тыб ещё про метод простыми вставками вспомнил
и чего ты хотел добиться подобными выкриками? любой из них весьма спорен.
1. "квиксорт форева". - пиздеж и провокация(я давно не писал в этот форум, меня забанят? )
не мог бы ты объяснить, с чего ты это взял? да, квиксорт отлично сортирует среднего размера порции данных(на небольших объемах слишком велики потери на организацию рекурсии, а на больших будет плохо стеку =)). худшее время квиксорта - n**2, тогда как у пирамидальной сортировки худшее время - n*(log2 n). и даже никаких программ писать не надо, все можно на пальцах посчитать.
2. причем тут метод простыми вставками? или это ты сказал чтобы сказать?

| Сообщение посчитали полезным:

Вы мне скажите расмер массива и размер улимента, я вам протестирую прям ща.
Ну чтоб на пальцАх не считать.

| Сообщение посчитали полезным:

ну не знаю, я вот курсовую когда делал, писал на С++ в консоли и реализовывал все это дело на массиве курсоров и в очереди и работала почти быстрей всех из группы, советую писать именно в консоли, ибо не тратится много машинного времени на побочные действия, производимые например Дельфи. аа... я делал кстати алгоритм Шелла, модифицация простых вставок

вот собственно

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

struct TLine {
int number;
int next;
} Line[5000];

int head1, tail1, head2=-1, tail2=-1, head3=-1, tail3=-1,head4=-1, tail4=-1,head5=-1, tail5=-1, head6=-1, tail6=-1, z,m, mm;

void ADD(int i, int* head, int* tail);
void DEL(int* head, int* tail);

void main()
{
int i,step[200], shag, numbchag,j,k,x,y,n,timer=0, mas[5000];

for (i=0; i<5000; i++)
{
mas[i]=rand();
}

_setcursortype(_NOCURSOR);
for (n=1000; n<=5000; n+=1000)
{
for (i=0; i<n; i++)
{
Line[i].next=i+1;
Line[i].number=mas[i];
}
head1=0;
tail1=n-1;
Line[tail1].next=-1;
step[i=0]=1;
while (n>(3*step[i]+1)) {
shag=3*step[i]+1;
i++;
step[i]=shag;
}
numbchag=i;

timer=clock();

for (i=numbchag; i>=0; i--)
{
for (j=0; j<=step[i]-1; j++)
{
for (k=0; k<j; k++)
{
x=head1;
DEL(&head1,&tail1);
ADD(x,&head2,&tail2);
}
x=head1;
DEL(&head1,&tail1);
ADD(x,&head3,&tail3);
z=1;
while (head1!=-1)
{
x=head1;
DEL(&head1,&tail1);
if (z==step[i])
{
ADD(x,&head3,&tail3);
z=1;
}
else
{
ADD(x,&head2,&tail2);
z++;
}
}
for (k=0; k<j; k++)
{
x=head2;
DEL(&head2,&tail2);
ADD(x,&head1,&tail1);
}
x=head3;
DEL(&head3,&tail3);
ADD(x,&head4,&tail4);
while(head3!=-1)
{
y=head3;
DEL(&head3,&tail3);
if (Line[x].number<=Line[y].number)
{
ADD(y,&head4,&tail4);
x=tail4;
}
else
{
while (head4!=x)
{
z=head4;
DEL(&head4,&tail4);
if (Line[y].number<=Line[z].number)
{
if (mm!=1)
{
ADD(y,&head5,&tail5);
mm=1;
}
}
ADD(z,&head5,&tail5);
}
x=head4;
DEL(&head4,&tail4);
while (head5!=-1)
{
z=head5;
DEL(&head5,&tail5);
ADD(z,&head4,&tail4);
}
if (mm!=1)
{
ADD(y,&head4,&tail4);
}
else
{
mm=0;
}
ADD(x,&head4,&tail4);
}
}
while (head4!=-1)
{
x=head4;
DEL(&head4,&tail4);
ADD(x,&head1,&tail1);
z=1;
while (z!=step[i])
{
if (head2==-1) { break;}
x=head2;
DEL(&head2,&tail2);
ADD(x,&head1,&tail1);
z++;
}
}
}

}
timer=clock()-timer;
cout << timer << endl;

}
getch();
}

void ADD(int i, int* head, int *tail)
{

if (*tail==-1)
{
*head=i;
*tail=i;
Line[i].next=-1;
}
else
{
Line[*tail].next=i;
Line[i].next=-1;
*tail=i;
}
}

void DEL(int* head, int* tail)
{

if ((*head==*tail))
{
*head=*tail=-1;
}
else
{
*head=Line[*head].next;
}
}



тебе остается только на обычные массивы переделать, а результаты в тиках(какие доли секунды точно не помню) следующие

40 - 1000 элементов
240 - 2000 элементов
431 - 3000 элементов
1272 - 4000 элементов
1692 - 5000 элементов

| Сообщение посчитали полезным:

NG спакойно
Да ладно пирамидальная сортировка всех отсартирует по самое нехочу.
(пошёл изучать пирамидальную сортировку)

2. причем тут метод простыми вставками? или это ты сказал чтобы сказать?
Ага

Данные имеют различную степень упорядоченности, совершенно разное количество приходится делать итераций и прочей хрени поэтому причём тут n*(log2 n), на практике всё нетак.

Ну шейкер не тоже самое что пузырьковая, всё таки она по производительней будет пузырьковой, могу на
500р поспорить

Ща хорошие исходники приатачу Сортировка слиянием (на основе квиксорт,С++), только найду.

-----
Никто не знает столько, сколько не знаю я

| Сообщение посчитали полезным:

см. аттач

5065_sorting.txt.zip

| Сообщение посчитали полезным:

Квиксорт рулит полюбому.
> 1. "квиксорт форева". - пиздеж и провокация(я давно не писал в этот форум, меня забанят? )
Забанять точно, я постораюсь. Потерями на рекурсию пугать может только тупой пионер (даже если есть рекурсия это микросекунды), или тупой препод - qsort лехко реализутся без рекурсии и будет явно на порядо кбустрее метода вставки. Кто не согласен - к барьеру быстро!

| Сообщение посчитали полезным:

ептить на то она и называется быстрой, что она быстрая, кто не согласен ну прочитайте Кнута

| Сообщение посчитали полезным:

DrGolova пишет:
qsort лехко реализутся без рекурсии и будет явно на порядо кбустрее метода вставки
а будет быстрее пирамидальной?

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным: