Кстати насчёт алгоритмов, есть идеи по быстрому удалению дубликатов в

Question

Ассемблер

Saenro

Кстати насчёт алгоритмов, есть идеи по быстрому удалению дубликатов в

массиве?

#assembler #programming #russian

0

20.01.2022

11 ответов

31 просмотр

CLFLUSH 🇷🇺 rdseed

Sergei Zhmylove
Когда нужно «быстро», обычно, о прочих затратах не...

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

0

20.01.2022

Alexander Morozov

А какие, собственно, есть еще варианты кроме формирования другого массива, в который элементы добавляются после проверки на отсутствие в нем?

0

20.01.2022

Saenro Автор вопроса

Sergei Zhmylove
Когда нужно «быстро», обычно, о прочих затратах не...

Да, с гигабайтами интереснее)

0

20.01.2022

CLFLUSH 🇷🇺 rdseed

Saenro
Да, с гигабайтами интереснее)

Ну покажи решение своё, чего тянуть

0

20.01.2022

Сергей

Alexander Morozov
А какие, собственно, есть еще варианты кроме форми...

1 проход: кэширование ключа каждого элемента и при встрече одинакового элемента (с кэшем сравнивать), помечать его на удаление. 2 проход: удаление удалённых элементов, копированием неудалённых. Идея в том, что кэш делать индексированным, для быстроты поиска. Мне кажется это было бы быстрее, чем искать в массиве дубле. Но это моя топорная идея и она очень далека от крутых алгоритмов

0

20.01.2022

Alexander Morozov

Сергей
1 проход: кэширование ключа каждого элемента и при...

Это просто оптимизация исходного варианта с целью экономии памяти. Будет плохо работать если имеем длинный массив с элементами малого размера.

0

20.01.2022

CLFLUSH 🇷🇺 rdseed

Сергей
1 проход: кэширование ключа каждого элемента и при...

Хорошая функция хэширования, а ещё и если её вызывать очень часто, может покрыть даже работу с памятью. Но всё же зависит от того, какая хэш-функция используется. CRC, вроде, не такой уж и затратный

0

20.01.2022

Сергей

Alexander Morozov
Это просто оптимизация исходного варианта с целью ...

Но 2 почти одинаковых массива, это тоже дорого (по памяти). Тогда может лучше исходный массив обходить, ища дубли после текущей позиции и при нахождении помечать на удаление?

0

20.01.2022

CLFLUSH 🇷🇺 rdseed

Сергей
Но 2 почти одинаковых массива, это тоже дорого (по...

Дубль может быть в самом начале и в самом конце

0

20.01.2022

Сергей

CLFLUSH 🇷🇺 rdseed
Дубль может быть в самом начале и в самом конце

Да. И тогда на первом шаге придётся пройтись по всему массиву

0

20.01.2022