ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Сортировка сотен миллионов строк с удалением дублей
55 сообщений из 55, показаны все 3 страниц
  все  
Сортировка сотен миллионов строк с удалением дублей
    #39833061
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
А что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые. Пока StringList с Sorted=true работает, но, возможно, медленно. Можно ли сделать что-то принципиально быстрее?
Использую несколько StringList'ов, чтобы разные записи, например, начинающиеся на разные буквы, сохранять в разных StringList'ах. Так, наверно, быстрее (сортировать несколько маленьких, чем один большой).
...
Рейтинг: 0 / 0
03.07.2019, 02:17
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833077
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
registeredА что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые. Пока StringList с Sorted=true работает, но, возможно, медленно. Можно ли сделать что-то принципиально быстрее?
Использую несколько StringList'ов, чтобы разные записи, например, начинающиеся на разные буквы, сохранять в разных StringList'ах. Так, наверно, быстрее (сортировать несколько маленьких, чем один большой).
В Вашем случае прямо таки напрашивается использование какой нибудь СУБД. Возможно встроенной, например SQLite или Firebird embedded.

Загоняете массив строк в табличку, а далее уже SQL выражениями делаете любую выборку. Все современные СУБД делают это очень быстро.
...
Рейтинг: 0 / 0
03.07.2019, 06:54
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833115
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
black-manatee,

СУБД?
Ради сортировки строк?
Реально?
...
Рейтинг: 0 / 0
03.07.2019, 10:12
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833127
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
registered,

Быстрей можно всегда, только это ручками делать надо.
Например побить свой лист на много более мелких. Так сортировка будет работать значительно быстрей.
...
Рейтинг: 0 / 0
03.07.2019, 10:34
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833140
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
registeredА что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые. Пока StringList с Sorted=true работает, но, возможно, медленно. Можно ли сделать что-то принципиально быстрее?
Использую несколько StringList'ов, чтобы разные записи, например, начинающиеся на разные буквы, сохранять в разных StringList'ах. Так, наверно, быстрее (сортировать несколько маленьких, чем один большой).1. фиговые дела происходят, блочное копирование
2. незначительно

метод сортировки в узких случаях нужно подбирать индивидуально, реализация сортировки в TSringList от дельфи, редкий позор
+ сортировка Хаора очень чувствительна к функции сравнения
...
Рейтинг: 0 / 0
03.07.2019, 11:10
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833153
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
var
  Basis: TArray<string>;
begin
  Randomize;
  SetLength(Basis, 10000000);
  for var k := Low(Basis) to High(Basis) do
    Basis[k] := Random(k).ToString();
 TArray.Sort<string>(Basis);


+ можно через TTask распараллелить по кускам и потом склеить, будет быстрее в зависимости от кол-ва ядер и процессоров.
...
Рейтинг: 0 / 0
03.07.2019, 11:30
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833176
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Я тут на коленке накидал распараллеливание, получил на 10 млн строк на 1 процессоре и 4 ядрах
в 1 поток заняло 10 секунд

разбиение на 4 равные части
сортировка каждой части на отдельном ядре
слияние 4 частей в 1 массив

заняло 5 секунд
...
Рейтинг: 0 / 0
03.07.2019, 11:54
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833181
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
X-Cite,

вся беда таких тестов что они не учитывают реальные данные и особенности алгоритмов
...
Рейтинг: 0 / 0
03.07.2019, 12:03
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833184
Tactical Nuclear Penguin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tactical Nuclear Penguin
Участник
X-CiteЯ тут на коленке накидал распараллеливание, получил на 10 млн строк на 1 процессоре и 4 ядрах
в 1 поток заняло 10 секунд

разбиение на 4 равные части
сортировка каждой части на отдельном ядре
слияние 4 частей в 1 массив

заняло 5 секунд

ты бы на нормальных строках делал, длиной хотя бы 50 знаков и из букв...
...
Рейтинг: 0 / 0
03.07.2019, 12:05
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833208
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
Дегтярев Евгенийblack-manatee,

СУБД?
Ради сортировки строк?
Реально?

Сортировка с выкидыванием дублей. TStringList так вроде не умеет.

А в чем собственно проблема ?
...
Рейтинг: 0 / 0
03.07.2019, 12:34
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833210
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
А можно еще хешик сделать. На первые несколько букв строки.
И сортировать по хэшу.
...
Рейтинг: 0 / 0
03.07.2019, 12:42
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833212
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
black-manatee,

То есть вы не видите проблемы?
...
Рейтинг: 0 / 0
03.07.2019, 12:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833217
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
black-manateeСортировка с выкидыванием дублей. TStringList так вроде не умеет.
Да ну правда что ли?
...
Рейтинг: 0 / 0
03.07.2019, 12:52
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833222
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Tactical Nuclear Penguinты бы на нормальных строках делал, длиной хотя бы 50 знаков и из букв...

Это не важно..
Цель была оценить распараллеливание по виртуальным процессорам.
...
Рейтинг: 0 / 0
03.07.2019, 12:54
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833270
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
Дегтярев Евгенийblack-manatee,

То есть вы не видите проблемы?

Озвучите
...
Рейтинг: 0 / 0
03.07.2019, 13:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833281
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
black-manatee,

оставим, что ради сортировки нужно в приложение притащить БД
пойдем дальше
ТС пишет что исходный вариант (сортировка в памяти) работает, но медленно
для примера возьмем результат X-Cite, у него сортировка заняла 10 сек
для начала сравните, плз, сколько у вас займет "загнять массив строк в таличку"
...
Рейтинг: 0 / 0
03.07.2019, 13:59
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833363
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
Дегтярев Евгенийblack-manatee,

оставим, что ради сортировки нужно в приложение притащить БД
пойдем дальше
ТС пишет что исходный вариант (сортировка в памяти) работает, но медленно
для примера возьмем результат X-Cite, у него сортировка заняла 10 сек
для начала сравните, плз, сколько у вас займет "загнять массив строк в таличку"

Думаю быстрее, чем сортировка (если загнать к примеру файл в блоб и скриптом или процедурой уже запихнуть в табличку).
Ну и сортировка будет точно быстрее.

Но вообще речь не об этом.
Человек работает с сотнями миллионов строк. Эти строки у него откуда то берутся (какие нибудь логи или что-то еще), записываются в какое-то хранилище (текстовые файлы), потом неким образом обрабатываются (сортируются и удаляются дубли), потом опять куда-то записываются (в те же или другие текстовые файлы), а затем очевидно где-то далее используются. То есть по сути речь идет о простой, но достаточно объемной БД, в качестве каковой registered использует текстовые файлы.
По моему очевидно, что использование СУБД в данном случае для всей этой байды реально напрашивается.
...
Рейтинг: 0 / 0
03.07.2019, 15:17
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833405
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
black-manateeПо моему очевидно, что использование СУБД в данном случае для всей этой байды реально напрашивается.
А мне очевидно что напрашивается ElasticSearch + Kibana
...
Рейтинг: 0 / 0
03.07.2019, 16:01
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833412
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Кстати, TArray.Sort сортирует в другом порядке, нежели StringList.
Пока что получилось, TArray где-то в 2 раза быстрее.

3327471 записей (98.1 мб)
25,125 сек - сорт StringList после загрузки
13,953 сек - сорт TArray<ansistring>

TArray - это то же самое, что и array of string? Мне этот синтаксис непривычен. Чем он хорош? Тем, что там есть Sort? А что мешало сделать отдельную функцию Sort для массива?
...
Рейтинг: 0 / 0
03.07.2019, 16:12
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833426
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
http://docwiki.embarcadero.com/Libraries/Rio/en/System.Generics.Collections.TArray

Это просто удобная обертка для статических дженериковских функций
...
Рейтинг: 0 / 0
03.07.2019, 16:26
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833430
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Ну и сам тип конечно...
http://docwiki.embarcadero.com/Libraries/Rio/en/System.TArray
...
Рейтинг: 0 / 0
03.07.2019, 16:28
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833528
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
StringList сортирует так, что одинаковые записи, различающиеся строчными и прописными буквами, будут соседними, а TArray - по коду символа, т.е., они будут в разных местах. Можно ли сделать, чтобы по-другому?
...
Рейтинг: 0 / 0
03.07.2019, 19:15
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833531
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
registered,

AnsiUpperCase.
...
Рейтинг: 0 / 0
03.07.2019, 19:28
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833550
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Там (в StringList) даже не посимвольно сравнивает, а, к примеру,
test031
и
test-03-1
будут вперемешку.

 
function TStringList.CompareStrings(const S1, S2: string): Integer;
begin
if CaseSensitive then
Result := AnsiCompareStr(S1, S2)
else
Result := AnsiCompareText(S1, S2);
end;


Добавил свой компаратор, такой:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
    comparer: IComparer<ansistring>;

      comparer := TDelegatedComparer<ansistring>.Create
       (
         function(const Left, Right: ansistring): Integer
         begin
            Result := AnsiCompareStr(Left,Right);
         end
      );

TArray.Sort<ansistring>(tarrstr,comparer);



Теперь сортирует так же, как StringList, но в 3 раза медленнее.
StringList - 9,641 сек
TArray.Sort (comparer) - 25,859 сек
TArray.Sort (по умолчанию) - 4,234 сек

Выборка та же, что и в прошлый раз, только тогда был комп загружен.

И зачем я всё это делал?
...
Рейтинг: 0 / 0
03.07.2019, 20:59
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833552
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
registeredИ зачем я всё это делал?Получил ценный опыт.
...
Рейтинг: 0 / 0
03.07.2019, 21:17
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833553
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
registered,

авторТеперь сортирует так же, как StringList, но в 3 раза медленнее.
мода требует жертв.
...
Рейтинг: 0 / 0
03.07.2019, 21:18
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833554
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
registeredТеперь сортирует так же, как StringList, но в 3 раза медленнее.
В одном случае сортируешь String, в другом AnsiString получаемые в результате конвертирования из String. Отсюда и просадка такая.
...
Рейтинг: 0 / 0
03.07.2019, 21:29
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833557
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Kazantsev Alexeyполучаемые в результате конвертирования из String
...наоборот, в смысле. Короче, замени AnsiString на String везде.
...
Рейтинг: 0 / 0
03.07.2019, 21:39
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833593
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Со String - 10,297 сек

Хотя уже переделал обратно в StringList
...
Рейтинг: 0 / 0
03.07.2019, 23:23
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833647
Фотография X11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X11
Участник
registeredStringList сортирует так, что одинаковые записи, различающиеся строчными и прописными буквами, будут соседними, а TArray - по коду символа, т.е., они будут в разных местах. Можно ли сделать, чтобы по-другому?

Думаю TDictionary тебя спасёт
...
Рейтинг: 0 / 0
04.07.2019, 09:04
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834311
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Kazantsev AlexeyKazantsev Alexeyполучаемые в результате конвертирования из String
...наоборот, в смысле. Короче, замени AnsiString на String везде.А почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.
...
Рейтинг: 0 / 0
05.07.2019, 12:30
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834315
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
registeredА почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.
Насколько я помню, всё современное API винды уже давно юникодовое, а когда используются старые вызовы (с суфиксом A) то внутри происходит преобразование в юникод и последующий вызов нужного юникодового метода. Таким образом, преобразование строк просто переносится на уровень системы.
...
Рейтинг: 0 / 0
05.07.2019, 12:38
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834506
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Я тут тест проводил

 
код теста
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
procedure Test;
const
  N = 10000000;
var
  Basis, Basis2: TArray<string>;
  k: Int32;
  sw: TStopwatch;

  function GetStr(const aLength: Int32): string;
  var
    k: Int32;
  begin
    SetLength(Result, aLength);
    for k := 1 to aLength do
      Result[k] := Chr(Random(150) + 32);
  end;

begin
  Randomize();
  SetLength(Basis, N);
  for k := Low(Basis) to High(Basis) do
    Basis[k] := GetStr(Random(50) + 20);
  SetLength(Basis2, N);
  TArray.Copy<string>(Basis, Basis2, N);

  sw := TStopwatch.StartNew();
  TArray.Sort<string>(Basis);
  sw.Stop();
  Memo1.Lines.Add('1 = ' + sw.ElapsedMilliseconds.ToString());

  sw := TStopwatch.StartNew();
  SortFast(Basis2); // Реализация на коленке разделения сортировки на X (где X = TThread.ProcessorCount) частей, где каждая часть использует TArray.Sort
  sw.Stop();
  Memo1.Lines.Add(TThread.ProcessorCount.ToString() + ' = ' + sw.ElapsedMilliseconds.ToString());
end;




 
Intel(R) Core(TM) i5-8600 CPU @ 3.10GHzIntel(R) Core(TM) i5-8600 CPU @ 3.10GHz
Сокетов: 1
Ядра: 6
Логических процессоров: 6
Виртуализация: Включено
Кэш L1: 384 КБ
Кэш L2: 1,5 МБ
Кэш L3: 9,0 МБ

1 = 8817 мс (В 1 поток)
6 = 4388 мс (В 6 потоков = кол-во логических процессоров)


 
Intel(R) Xeon(R) Gold 6146 CPU @ 3.20GHzIntel(R) Xeon(R) Gold 6146 CPU @ 3.20GHz
Сокетов: 2
Ядра: 24
Логических процессоров: 24
Виртуализация: Отключено
Поддержка Hyper-V: Да
Кэш L1: 1,5 МБ
Кэш L2: 24,0 МБ
Кэш L3: 49,5 МБ

1 = 13992 мс (В 1 поток)
24 = 7560 мс (В 24 потока = кол-во логических процессоров)
Здесь был интересный момент. Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.


 
Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHzIntel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz
Сокетов: 4
Виртуальные процессоры: 16
Виртуальная машина: Да
Кэш L1: Н/Д

1 = 41553 мс (В 1 поток)
16 = 13800 мс (В 16 потоков = кол-во виртуальных процессоров)
...
Рейтинг: 0 / 0
05.07.2019, 23:24
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834508
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
А разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.
...
Рейтинг: 0 / 0
05.07.2019, 23:32
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834509
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
registeredА разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.
Merge sort уже отменили?
...
Рейтинг: 0 / 0
05.07.2019, 23:33
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834511
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Кстати... Можно сделать merge sort и проверить результат...

Потому что моя цель была разделить именно на N частей и сделать TArray.Sort каждой части в своей таске, а потом их склеить через merge join

По сути:
1) Делим 1 массив на N - выполняется в одном потоке
2) Сортируем N частей в N тасках. При этом надеемся TThreadPool корректно их распихал в N потоков. А ОС корректно их разнесла по процессорам/ядрам.
3) Ждем всех, чтобы сделать merge join
4) Делаем merge join из N массивов в 1.
...
Рейтинг: 0 / 0
05.07.2019, 23:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834534
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
white_nigger
Участник
X-Cite,

Что-то у тебя плохо масштабируется по ядрам. Сейчас проверил твой пример на своей версии из dxThreading на своем ноуте:

1 = 11641
8 = 3126

i7-4710HQ 2.5GHz
...
Рейтинг: 0 / 0
06.07.2019, 01:15
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834543
Голландец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Голландец
Участник
registered,

Ты не послушаешь, но это правда самые быстрые способы.

1. Добавить строки в TStringList(а лучше в динамический массив, предварительно установив длину). Отсортировать. Пройтись от последнего к первому и удалить дубликаты. Есть более продвинутый способ удаления дубликатов, но ты его, скорее всего не потянешь )

2. Сделать TDictionary и выполнять AddOrSetValue. Потом сделать ToArray и отсортировать массив.

Если дубликатов много - лучше сработает первый способ. Если мало - второй. Можно извратиться и взять Rapid.Generics - там сортировки и словари быстрее.
...
Рейтинг: 0 / 0
06.07.2019, 07:52
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834544
Голландец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Голландец
Участник
Голландец,

Наоборот. Дубликатов мало - первый способ. Много - словари )
...
Рейтинг: 0 / 0
06.07.2019, 07:55
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834547
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Вообще-то, у TStringList есть свойство Duplicates, которое можно выставить в dupIgnore. Также у него есть свойство Capacity.
...
Рейтинг: 0 / 0
06.07.2019, 08:56
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834559
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
registered,

сколько у тебя различных строк после отсева дубликатов в реальных данных?
...
Рейтинг: 0 / 0
06.07.2019, 10:46
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834586
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
white_nigger,

Потому что на коленке писаная за 10 минут для этого топика)
...
Рейтинг: 0 / 0
06.07.2019, 13:14
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834606
MaratIsk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MaratIsk
Участник
registered,

чо-то 100 лямов мало :(
надо не ниже 3,5 лярдов, а лучше 5 (с запасом, так сказать)
...
Рейтинг: 0 / 0
06.07.2019, 14:29
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834706
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
white_nigger
Участник
X-Cite,
Понятно. Кстати, возможно у меня использовались только 4 ядра. Надо будет по коду глянуть. Я уже не помню как рассчитывал количество потоков
...
Рейтинг: 0 / 0
07.07.2019, 13:04
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834720
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
white_niggerX-Cite,
Понятно. Кстати, возможно у меня использовались только 4 ядра. Надо будет по коду глянуть. Я уже не помню как рассчитывал количество потоков
Я не думал, просто взял кол-во задач = кол-ву логических процессоров, хотя можно поиграться...
Параллелилось норм... я же merge сделал в основном потоке, не параллелил его и в лоб к тому же, а не по книжке....
Да и копирование можно было сделать в своем чанке... еще 100 мс сэкономить...

19368 - основной поток

07.07.2019 14:58:59.747; 19368: ->Run
07.07.2019 14:58:59.887; 19368: Copy = 125
07.07.2019 14:59:01.846; 5472: Chunk1 = 1958
07.07.2019 14:59:01.876; 16680: Chunk2 = 1989
07.07.2019 14:59:01.888; 5364: Chunk3 = 2006
07.07.2019 14:59:01.896; 10712: Chunk4 = 2011
07.07.2019 14:59:01.896; 12284: Chunk5 = 2014
07.07.2019 14:59:01.922; 15260: Chunk6 = 2037
07.07.2019 14:59:01.922; 19368: All wait = 2037
07.07.2019 14:59:04.259; 19368: merge = 2338
07.07.2019 14:59:04.259; 19368: <-Run

Основной посыл был в том, что даже на коленке наспех реализация распараллеливания сортировки выгоднее.
А не прочитали в книжке 199x года, что есть вот такой "замечательный" TStringList и давай его везде пихать...
...
Рейтинг: 0 / 0
07.07.2019, 15:02
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834729
Голландец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Голландец
Участник
X-Cite,

QuickSort на выходе может дать 2 диапазона. Один можно продолжить выполнять в том же потоке, а второй - отдать в пул. Тогда не придётся делать мердж.
...
Рейтинг: 0 / 0
07.07.2019, 15:34
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834734
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Поскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна. Хэш-таблица
даёт тот же результат, но имеет O(1) вместо O(N*log2(N)).
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
07.07.2019, 16:15
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834737
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Dimitry SibiryakovПоскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна.
Хм...
https://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1314494&msg=21919544 А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые.
...
Рейтинг: 0 / 0
07.07.2019, 16:17
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834755
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?
...
Рейтинг: 0 / 0
07.07.2019, 17:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834816
Фотография Критик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Критик
Участник
1) проанализировать, откуда эти строки, собственно, берутся, может проще исключить возникновение дублей
2) проанализировать задачу, можно ли ее решить в другом слое приложения - в той же упомянутой СУБД
3) если ничего не поучилось, то сортировать в приложении, но это поражение
...
Рейтинг: 0 / 0
07.07.2019, 23:48
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834877
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Дегтярев Евгений> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?
Да
...
Рейтинг: 0 / 0
08.07.2019, 09:33
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39835264
Фотография Gator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gator
Участник
X-CiteДегтярев Евгений> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?
Да
Вроде бы Тема о сортировке большых(?) объёмах данных? На клиенте?
А вы тут... PUMA зачем-то... Вы бы ещё IBM & Cray Corp вспомнили...
SAS мозгололомоы разбежались по конторам по тематике...
___
Собственно вопрос. Кто в состоянии обработать 100 миллионов строк (а завтра и 100 миллиардов)?
Тут нужен сервис ленивый (а ля LazyReader/LazyWriter)
Клиенту-то это зачем?
Распределённая сеть с распределёнными транзакциями ради тупой сортировки(?) неизвестно чего(ТС?)???
Да ещё на Дельфи? Не верю!

Клиент пусть берёт нужную выборку из своего OLAP и сортирует,
как жопса скажет нужные ему поля в нужном ему порядке
______________
...
Рейтинг: 0 / 0
09.07.2019, 00:23
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39835291
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
GatorА вы тут... PUMA зачем-то...
whaat?
...
Рейтинг: 0 / 0
09.07.2019, 07:34
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39835362
Фотография Gator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gator
Участник
Дегтярев Евгений,
Pardon, NUMA
...
Рейтинг: 0 / 0
09.07.2019, 11:23
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39835505
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Gator,

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

К тому же в своих тестах привел кейс для своей машины, считай клиентской, и для двух разных серверов. Моя выиграла из-за того что частота CPU выше, хотя я пробовал на физическом сервере с такой же частотой и он все равно медленнее оказался. Виртуальные серверы понятно, что проиграли.
А вопрос про NUMA возник из-за того, что меня удивило, что 24 ЛП не напрягались, и как я понял это может быть причиной, когда данные оказались в памяти не того сокета, куда прикреплен процессор.

Никакие распределенные сети не нужны. Нужно чтобы TArray.Sort<T> работал быстро неважно где и использовал все возможности машины на которой выполняется код.

P.S.
Создал в QC 3 таски:
Одна на multithreading сортировку в TArray.Sort<T> - добавить возможность включения
Одна на поддержку NUMA в менеджере памяти - актуально для бэкенда (на гитхабе нашел коммент в FastMM на поддержку, но он так и остался комментом [planned: support for multiple per-NUMA-node allocators])
Одна на поддержку NUMA в TThredPool - актуально для бэкенда
...
Рейтинг: 0 / 0
09.07.2019, 15:15
| Ответить | Цитировать | Написать  
55 сообщений из 55, показаны все 3 страниц
  все  
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Сортировка сотен миллионов строк с удалением дублей
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=58&tid=2039285]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 175ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 65ms
get tp. blocked users:
 1ms
others: 227ms
total:  511ms
созд. / загр.: 511ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]