Спасибо большое за Ваши статьи, очень интересно и позновательно!
<сарказм>
Однако во время чтения меня постоянно преследовала одна мысль:
В вашем изложении радиоактивные материалы не опаснее короновируса, если использовать маску и дистанцирование.
</сарказм>
Подскажите ответ на давно мучащий вопрос: возможно ли использовать посадку ракеты с винтом, по-вертолётному в режиме авто-ротации? Подобно тому, как приземляются семена клёна.
Вы задумывались, кому нужен тот мусор что мы оставим после себя?
Фоточки в инстаграм, или кучу бессмысленного кода который устареет ещё при вашей жизни. Только осознавать сам процесс существования, только в этом есть смысл.
Ребят Вы конечно крутые и реализация интересная, однако мне кажется, Вы всё несколько переусложнили.
По моему мнению, нужно было делать проще:
У Вас каждое объявление имеет координату по широте и долготе.
Переводим Широту и долготу в экранные координаты в проекции Меркатора на самом большём уровне приближения для карт, и храним в БД и Кэшируем по необходимости.
(в принципе можно не переводить координаты, а рассчитывать на лету во фронте, но при большём количестве точек будут явные просадки).
При выводе карты отправляем запрос с БД на выбор точек (можно кэшировать). Затем отрисовываем слой svg c токенами поверх карты. А при нажатии мышкой выбирать в окрестности нажатия ближайший токен и обрабатывать выдачу.
В своём старом проекте уже реализовывал подобную схему. Более ста тысяч точек спокойно обрабатывается на одном экране. Только это был Pascal, а не javascript.
На счёт веселее тут Вы правы. Но вся индустрия разработки давит на скорость обработки, в основном выравниванием стека, улучшением предсказания ветвлений, реже векторизацией, зачастую сильно завышенными затратами памяти.
Я когда смотрю на современные языки типа Python, которые насилуют память, сверх не эффективно её используя, просто сердце щемит. Однако согласитесь, работает все очень быстро, на типовых задачах.
Вы бы подробнее рассказали про проект, в котором нужно искать пересечение миллиона множеств.
И при таких объёмах данных разумнее мне кажется разделить множества на подмножества, и обрабатывать их по лимиту оперативной памяти.
На мой взгляд, если массивы сильно разряженные, лучше использовать список с указателем на следующий (и предыдущий) элемент.
Если списки достаточно плотные от 50% заполнения то самый выгодный вариант будет использовать массив подсчёта. 1 в каждом бите, если элемент есть и 0, если не существует. Как уже писали выше если int значение, то потребуется 500Мбайт накладных расходов, если только положительные числа — в два раза меньше.
Всё что Вы описали выше интересно с академической точки, но сомневаюсь, что в реальном проекте даже 2х-4х кратная экономия по памяти ценой таких накладных расходов оправдана.
В одном проекте где потребовалось подсчитывать все int значения со счётчиком, я просто докупил памяти до 16 гб.
Последовательный расчёт 5000 маршрутов типа точка-точка ущербен изначально.
Тем более что алгоритм Дейкстры по умолчанию строит связь со всеми узлами. Нужно лишь продолжать поиск пока не будут посещены все узлы. Задача оптимизации полученной матрицы это уже отдельная задача. Просто оставлю ссылку.
Кстати да. Не эксперт по хэшам, но что мешает взять сразу два разных алгоритма формирования хэша, даже 32 битных. И считать вхождение только если срабатывают сразу оба?
Я вам больше того скажу, даже 4 Гб не понадобиться.
Решал подобную задачу для 32-битных целых чисел. Там по факту требуется только возвести флаг – 1бит. Итого 0.5GB на вспомогательный массив. Основной же массив ограничен только оперативкой, ну или делать с подкачкой блоками из файла.
Работает быстро.
Мой пример на Pascal
// Сортировка подсчётом с удалением повторов
procedure Sort_Counting_Unique(var m: array of longword);
const max = 256 * 256 * 256 * 8;
var
s: array of longword;
i, j, k: longword; // Переменные, играющие роль индексов
offset1, offset2: longword; // Смещения
begin
SetLength(s, max);
FillChar(s[0], max * SizeOf(Longword), 0); // Обнуление вспомогательного массива
for i := 0 to Length(m)-1 do // Заполняем массив подсчётов
begin
offset1 := m[i] shr 5; // Id ячейки в спомогательном массиве
offset2 := 1 shl (m[i] and 31); // Cмещение бита в ячейке
s[offset1] := s[offset1] or offset2; // Сохраняем ячейку с взведённым битом
end;
j := 0;
for i := 0 to max-1 do // Сохраняем отсортированный массив, повторы игнорируются
if s[i] <> 0 then // Пропускаем пустые ячейки для ускорения
for k := 0 to 31 do
if ((s[i] shr k) and 1) > 0 then
begin
m[j] := i * 32 + k;
Inc(j);
end;
FillChar(m[j], (Length(m)-j) * SizeOf(Longword), 0); // Зануляем оставщуюся часть массива очищенного от повторов
SetLength(s, 0);
end;
По самой статье было очень интересно. Особенно в части простоя при загрузке данных в кэш процессора, сам приходил к подобным выводам.
Ну да, в зависимости от массы получится не хилый такой взрыв. Тогда лучше делать противовес из сферы заполненной водой. Выйдя из установки, сфера должна раскрыться на две полусферы, вода испариться не долетев до земли, а ущерб экологии от стали будет минимальным.
На счёт высоты и разреженности воздуха — сняли идею с языка.
А если организовать установку на вершине горы, у подножья которой есть озеро c западной строны, то можно не заморачиваться с утилизацией противовеса. Вода впитает кинетику выброса противовеса, правда будет много брызг.
Воспринял статью как неструктурированный поток сознания, который зациклил мои логические вентили и отправил мозг в reboot, в этот момент меня проняло.
Отличный арт. для пятницы.
По поводу написанного: Мы пришли в эту игру, чтоб преодолевать физические и ментальные ограничения. Убери из системы карму как набор причинно-следственных связей, у играющего потеряется интерес к процессу. God-mode режим приведёт систему к коллапсу. Идеален медленный итерационный процесс развития сознания путём проб и ошибок.
Система подавления не так уж и ущербна, она оберегает человечество от опасных флуктуаций отдельных индивидов с раздутым самомнением о своей божественной природе. Но с развитием трансцендентной личности перестаёт оказывать сильное значение на индивида.
Аналогия: игра в рогалики. Изначально ты умираешь постоянно на каждом шагу, но с опытом игры многие ловушки тебе не опасны, и ты проходишь до финала.
Резюмирую: Это план хардкор’а, слабаки тут не играют.
Пробовал с проходом по 4 бита, падение 30-40%, видимо тут уже кэш не даёт такого преимущества как встроенные инструкции процессора на 1 байтовые вычисления и повторные проходы.
Есть желание опробовать гибрид MSD и LSD для разных проходов, если будут интересные результаты, напишу.
Вариант с отдельной функцией сортировки на последнем шаге, падение меньше около 4-5%, уже приемлемо.
код
//==================================================
procedure RSort2(var m: array of Longword);
//--------------------------------------------------
procedure Sort_step(var source, dest, s_source, s_dest: array of Longword; const num: Byte);
var i,temp : Longword;
k,num1,num2 : Byte;
offset : array[0..3] of byte absolute temp;
begin
num2 := num+1; // устанавливаем байт для проверки на следующем шаге
for i := 1 to 255 do // Пересчёт смещений для текущей корзины
Inc(s_source[i], s_source[i-1]);
FillChar(s_dest, 256 * SizeOf(Longword), 0);
num1 := num*8;
for i := High(source) downto 0 do
begin
temp := source[i];
Inc(s_dest[offset[num2]]);
k := temp SHR num1;
Dec(s_source[k]);
Dest[s_source[k]] := temp;
end;
end;
//--------------------------------------------------
procedure Sort_step_last(var source, dest, s_source : array of Longword);
var i,temp : Longword;
k : Byte;
begin
for i := 1 to 255 do // Пересчёт смещений для текущей корзины
Inc(s_source[i], s_source[i-1]);
for i := High(source) downto 0 do
begin
temp := source[i];
k := temp SHR 24;
Dec(s_source[k]);
Dest[s_source[k]] := temp;
end;
end;
//--------------------------------------------------
var s : array[0..1] of array[0..255] of Longword; // Объявляем массив двух корзин первым, для выравнивания на стеке
i : longword;
k : Byte;
m_temp : array of Longword;
begin
SetLength(m_temp, Length(m)); // Объявляем временный массив
FillChar(s[0], 256 * SizeOf(Longword), 0); // Быстрая очистка первой корзины
for i := 0 to High(m) do // Заполнение первой корзины
begin
k := m[i];
Inc(s[0,k]);
end;
Sort_step(m, m_temp, s[0], s[1], 0); // Вызов сортировки по байтам от младших к старшим
Sort_step(m_temp, m, s[1], s[0], 1);
Sort_step(m, m_temp, s[0], s[1], 2);
Sort_step_last(m_temp, m, s[1]);
SetLength(m_temp, 0); // Высвобождаем память
end;
//==================================================
Падение скорости получилась в среднем на 13% при n>1000, стоит ли это 2Кб памяти, сомнительно.
На меньших длинах есть небольшой выигрыш. Возможно данный код поддаётся улучшению.
Код
//======================================================
procedure RSort2(var m: array of Longword);
//--------------------------------------------------
procedure Sort_step(var source, dest, s_source, s_dest: array of Longword; const num: Byte);
var i,temp : Longword;
k,num1,num2 : Byte;
offset : array[0..3] of byte absolute temp;
begin
if num<3 then // устанавливаем байт для проверки на следующем шаге
num2 := num+1
else
num2:=0;
for i := 1 to 255 do // Пересчёт смещений для текущей корзины
Inc(s_source[i], s_source[i-1]);
FillChar(s_dest, 256 * SizeOf(Longword), 0);
num1 := num*8;
for i := High(source) downto 0 do
begin
temp := source[i];
Inc(s_dest[offset[num2]]);
k := temp SHR num1;
Dec(s_source[k]);
Dest[s_source[k]] := temp;
end;
end;
//------------------------------------------------------------------------------
var s : array[0..1] of array[0..255] of Longword; // Объявляем массив двух корзин первым, для выравнивания на стеке
i : longword;
k : Byte;
m_temp : array of Longword;
begin
SetLength(m_temp, Length(m)); // Объявляем временный массив
FillChar(s[0], 256 * SizeOf(Longword), 0); // Быстрая очистка первой корзины
for i := 0 to High(m) do // Заполнение первой корзины
begin
k := m[i];
Inc(s[0,k]);
end;
Sort_step(m, m_temp, s[0], s[1], 0); // Вызов сортировки по байтам от младших к старшим
Sort_step(m_temp, m, s[1], s[0], 1);
Sort_step(m, m_temp, s[0], s[1], 2);
Sort_step(m_temp, m, s[1], s[0], 3);
SetLength(m_temp, 0); // Высвобождаем память
end;
//======================================================
Если только для следующего разряда, то да, сработает.
Хотя немного собьёт стройность конструкции, ведь что тогда считать на последнем шаге, видимо добавить проверку на не исполнение.
Мысль мне нравиться попробую посмотрю на изменение производительности.
<сарказм>
Однако во время чтения меня постоянно преследовала одна мысль:
В вашем изложении радиоактивные материалы не опаснее короновируса, если использовать маску и дистанцирование.
</сарказм>
Фоточки в инстаграм, или кучу бессмысленного кода который устареет ещё при вашей жизни. Только осознавать сам процесс существования, только в этом есть смысл.
По моему мнению, нужно было делать проще:
У Вас каждое объявление имеет координату по широте и долготе.
Переводим Широту и долготу в экранные координаты в проекции Меркатора на самом большём уровне приближения для карт, и храним в БД и Кэшируем по необходимости.
(в принципе можно не переводить координаты, а рассчитывать на лету во фронте, но при большём количестве точек будут явные просадки).
При выводе карты отправляем запрос с БД на выбор точек (можно кэшировать). Затем отрисовываем слой svg c токенами поверх карты. А при нажатии мышкой выбирать в окрестности нажатия ближайший токен и обрабатывать выдачу.
В своём старом проекте уже реализовывал подобную схему. Более ста тысяч точек спокойно обрабатывается на одном экране. Только это был Pascal, а не javascript.
Я когда смотрю на современные языки типа Python, которые насилуют память, сверх не эффективно её используя, просто сердце щемит. Однако согласитесь, работает все очень быстро, на типовых задачах.
И при таких объёмах данных разумнее мне кажется разделить множества на подмножества, и обрабатывать их по лимиту оперативной памяти.
Если списки достаточно плотные от 50% заполнения то самый выгодный вариант будет использовать массив подсчёта. 1 в каждом бите, если элемент есть и 0, если не существует. Как уже писали выше если int значение, то потребуется 500Мбайт накладных расходов, если только положительные числа — в два раза меньше.
Всё что Вы описали выше интересно с академической точки, но сомневаюсь, что в реальном проекте даже 2х-4х кратная экономия по памяти ценой таких накладных расходов оправдана.
В одном проекте где потребовалось подсчитывать все int значения со счётчиком, я просто докупил памяти до 16 гб.
Тем более что алгоритм Дейкстры по умолчанию строит связь со всеми узлами. Нужно лишь продолжать поиск пока не будут посещены все узлы. Задача оптимизации полученной матрицы это уже отдельная задача.
Просто оставлю ссылку.
Не хочу каркать, но здравый смысл подсказывает, что нас ждёт месячник короновируса, а то и пара-тройка.
Решал подобную задачу для 32-битных целых чисел. Там по факту требуется только возвести флаг – 1бит. Итого 0.5GB на вспомогательный массив. Основной же массив ограничен только оперативкой, ну или делать с подкачкой блоками из файла.
Работает быстро.
procedure Sort_Counting_Unique(var m: array of longword);
const max = 256 * 256 * 256 * 8;
var
s: array of longword;
i, j, k: longword; // Переменные, играющие роль индексов
offset1, offset2: longword; // Смещения
begin
SetLength(s, max);
FillChar(s[0], max * SizeOf(Longword), 0); // Обнуление вспомогательного массива
for i := 0 to Length(m)-1 do // Заполняем массив подсчётов
begin
offset1 := m[i] shr 5; // Id ячейки в спомогательном массиве
offset2 := 1 shl (m[i] and 31); // Cмещение бита в ячейке
s[offset1] := s[offset1] or offset2; // Сохраняем ячейку с взведённым битом
end;
j := 0;
for i := 0 to max-1 do // Сохраняем отсортированный массив, повторы игнорируются
if s[i] <> 0 then // Пропускаем пустые ячейки для ускорения
for k := 0 to 31 do
if ((s[i] shr k) and 1) > 0 then
begin
m[j] := i * 32 + k;
Inc(j);
end;
FillChar(m[j], (Length(m)-j) * SizeOf(Longword), 0); // Зануляем оставщуюся часть массива очищенного от повторов
SetLength(s, 0);
end;
По самой статье было очень интересно. Особенно в части простоя при загрузке данных в кэш процессора, сам приходил к подобным выводам.
А если организовать установку на вершине горы, у подножья которой есть озеро c западной строны, то можно не заморачиваться с утилизацией противовеса. Вода впитает кинетику выброса противовеса, правда будет много брызг.
Отличный арт. для пятницы.
По поводу написанного: Мы пришли в эту игру, чтоб преодолевать физические и ментальные ограничения. Убери из системы карму как набор причинно-следственных связей, у играющего потеряется интерес к процессу. God-mode режим приведёт систему к коллапсу. Идеален медленный итерационный процесс развития сознания путём проб и ошибок.
Система подавления не так уж и ущербна, она оберегает человечество от опасных флуктуаций отдельных индивидов с раздутым самомнением о своей божественной природе. Но с развитием трансцендентной личности перестаёт оказывать сильное значение на индивида.
Аналогия: игра в рогалики. Изначально ты умираешь постоянно на каждом шагу, но с опытом игры многие ловушки тебе не опасны, и ты проходишь до финала.
Резюмирую: Это план хардкор’а, слабаки тут не играют.
Есть желание опробовать гибрид MSD и LSD для разных проходов, если будут интересные результаты, напишу.
Затем, беспилотные автомобили, квадрокоптеры и прочие робо-мулы захватили сферу доставки.
Умные пылесосы и виртуальные ассистенты совместно с сетями глубокого обучения заняли сферу услуг.
Всё что осталось человечеству — это майнить виртуальную криптовалюту, на виртуальных же рудниках.
Апокалипсис оказался ближе, чем мы думали…
….
До производства первого T1000 оставалось менее 15 лет….
На меньших длинах есть небольшой выигрыш. Возможно данный код поддаётся улучшению.
Хотя немного собьёт стройность конструкции, ведь что тогда считать на последнем шаге, видимо добавить проверку на не исполнение.
Мысль мне нравиться попробую посмотрю на изменение производительности.