Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
makhaon
Member

Откуда: A galaxy far far away
Сообщений: 3260
registered,

автор
Теперь сортирует так же, как StringList, но в 3 раза медленнее.

мода требует жертв.
3 июл 19, 21:18    [21920262]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3543
registered
Теперь сортирует так же, как StringList, но в 3 раза медленнее.

В одном случае сортируешь String, в другом AnsiString получаемые в результате конвертирования из String. Отсюда и просадка такая.
3 июл 19, 21:29    [21920264]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3543
Kazantsev Alexey
получаемые в результате конвертирования из String

...наоборот, в смысле. Короче, замени AnsiString на String везде.
3 июл 19, 21:39    [21920267]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 42
Со String - 10,297 сек

Хотя уже переделал обратно в StringList
3 июл 19, 23:23    [21920351]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X11
Member

Откуда: Kharkiv, Ukraine
Сообщений: 13038
registered
StringList сортирует так, что одинаковые записи, различающиеся строчными и прописными буквами, будут соседними, а TArray - по коду символа, т.е., они будут в разных местах. Можно ли сделать, чтобы по-другому?


Думаю TDictionary тебя спасёт
4 июл 19, 09:04    [21920452]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 42
Kazantsev Alexey
Kazantsev Alexey
получаемые в результате конвертирования из String

...наоборот, в смысле. Короче, замени AnsiString на String везде.
А почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.
5 июл 19, 12:30    [21921518]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3543
registered
А почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.

Насколько я помню, всё современное API винды уже давно юникодовое, а когда используются старые вызовы (с суфиксом A) то внутри происходит преобразование в юникод и последующий вызов нужного юникодового метода. Таким образом, преобразование строк просто переносится на уровень системы.
5 июл 19, 12:38    [21921523]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1435
Я тут тест проводил

+ код теста
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.10GHz
Intel(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.20GHz
Intel(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.40GHz
Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz
Сокетов: 4
Виртуальные процессоры: 16
Виртуальная машина: Да
Кэш L1: Н/Д

1 = 41553 мс (В 1 поток)
16 = 13800 мс (В 16 потоков = кол-во виртуальных процессоров)
5 июл 19, 23:24    [21921854]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 42
А разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.
5 июл 19, 23:32    [21921861]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 57398
Блог
registered
А разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.

Merge sort уже отменили?
5 июл 19, 23:33    [21921862]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1435
Кстати... Можно сделать merge sort и проверить результат...

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

По сути:
1) Делим 1 массив на N - выполняется в одном потоке
2) Сортируем N частей в N тасках. При этом надеемся TThreadPool корректно их распихал в N потоков. А ОС корректно их разнесла по процессорам/ядрам.
3) Ждем всех, чтобы сделать merge join
4) Делаем merge join из N массивов в 1.
5 июл 19, 23:43    [21921869]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
white_nigger
Member

Откуда: Тула
Сообщений: 2114
X-Cite,

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

1 = 11641
8 = 3126

i7-4710HQ 2.5GHz
6 июл 19, 01:15    [21921898]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Голландец
Member

Откуда:
Сообщений: 98
registered,

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

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

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

Если дубликатов много - лучше сработает первый способ. Если мало - второй. Можно извратиться и взять Rapid.Generics - там сортировки и словари быстрее.
6 июл 19, 07:52    [21921914]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Голландец
Member

Откуда:
Сообщений: 98
Голландец,

Наоборот. Дубликатов мало - первый способ. Много - словари )
6 июл 19, 07:55    [21921915]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3543
Вообще-то, у TStringList есть свойство Duplicates, которое можно выставить в dupIgnore. Также у него есть свойство Capacity.
6 июл 19, 08:56    [21921922]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1742
registered,

сколько у тебя различных строк после отсева дубликатов в реальных данных?
6 июл 19, 10:46    [21921951]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1435
white_nigger,

Потому что на коленке писаная за 10 минут для этого топика)
6 июл 19, 13:14    [21921997]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
MaratIsk
Member

Откуда: Astana, Kazakhstan
Сообщений: 2468
registered,

чо-то 100 лямов мало :(
надо не ниже 3,5 лярдов, а лучше 5 (с запасом, так сказать)
6 июл 19, 14:29    [21922021]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
white_nigger
Member

Откуда: Тула
Сообщений: 2114
X-Cite,
Понятно. Кстати, возможно у меня использовались только 4 ядра. Надо будет по коду глянуть. Я уже не помню как рассчитывал количество потоков
7 июл 19, 13:04    [21922214]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1435
white_nigger
X-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 и давай его везде пихать...
7 июл 19, 15:02    [21922238]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Голландец
Member

Откуда:
Сообщений: 98
X-Cite,

QuickSort на выходе может дать 2 диапазона. Один можно продолжить выполнять в том же потоке, а второй - отдать в пул. Тогда не придётся делать мердж.
7 июл 19, 15:34    [21922247]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47660

Поскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна. Хэш-таблица
даёт тот же результат, но имеет O(1) вместо O(N*log2(N)).

Posted via ActualForum NNTP Server 1.5

7 июл 19, 16:15    [21922253]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3543
Dimitry Sibiryakov
Поскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна.

Хм...
https://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1314494&msg=21919544
А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые.
7 июл 19, 16:17    [21922256]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1605
> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?
7 июл 19, 17:43    [21922278]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Критик
Member

Откуда: Москва / Калуга
Сообщений: 31763
Блог
1) проанализировать, откуда эти строки, собственно, берутся, может проще исключить возникновение дублей
2) проанализировать задачу, можно ли ее решить в другом слое приложения - в той же упомянутой СУБД
3) если ничего не поучилось, то сортировать в приложении, но это поражение
7 июл 19, 23:48    [21922367]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Delphi Ответить