Справка - Поиск - Участники - Войти - Регистрация
Полная версия: Идентифицировать последовательность чисел
Частный клуб Алекса Экслера > Программирование
Constantin
25 августа 2016, 17:41
Есть несколько последовательностей чисел, например:
1. 12,15,0,0,18,21,0,0,0,25
2. 0,12,0,15,18,0,0,21,25,0

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

Есть ли какой-то несложный алгоритм, по которому можно отличить последовательности, приведенные в примере? Что-то типа контрольной суммы?
Mx
25 августа 2016, 22:39

Constantin написал:
Специально привел для примера последовательности с одинаковыми числами, но расположенные в другом порядке.

И что должен показывать этот пример? Эти последовательности по условиям задачи считаются одинаковыми, или нет?


Есть ли какой-то несложный алгоритм, по которому можно отличить последовательности, приведенные в примере? Что-то типа контрольной суммы?

Чем не устраивает простое поэлементное сравнение до нахождения первой пары отличных элементов, или исчерпания всех элементов?
Timmy
26 августа 2016, 00:35

Constantin написал:
Есть ли какой-то несложный алгоритм, по которому можно отличить последовательности, приведенные в примере? Что-то типа контрольной суммы?

Конечно. Например, контрольные суммы.
Нужно больше подробностей, чтобы можно было подобрать хороший инструмент.

Mx написал: Чем не устраивает простое поэлементное сравнение до нахождения первой пары отличных элементов, или исчерпания всех элементов?

Ну, например, эти последовательности могут быть большими, и их может быть много, и появляться они могут не одновременно. Например, у тебя есть миллион последовательностей по миллиону чисел. Пришла новая. Тебе нужно определить, была такая уже или нет. Ты ж не будешь все их хранить в памяти...
Constantin
26 августа 2016, 01:35

Mx написал: И что должен показывать этот пример? Эти последовательности по условиям задачи считаются одинаковыми, или нет?

Они должны считаться разными.

Timmy написал: Конечно. Например, контрольные суммы.
Нужно больше подробностей, чтобы можно было подобрать хороший инструмент.

Нужны именно контрольные суммы или хэш. Они потом будут передаваться дальше, для другой обработки и контроля.
Последовательности небольшие (до 200 чисел), но одинаковые на момент проверки.
Timmy
26 августа 2016, 03:13

Constantin написал:
Последовательности небольшие (до 200 чисел), но одинаковые на момент проверки.

А что-нибудь еще про них известно? Если нет, попробуй, например, MD5 или SHA-1. Не забывай, что хэши разных последовательностей теоретически могут совпадать.
Constantin
26 августа 2016, 04:50

Timmy написал: А что-нибудь еще про них известно? Если нет, попробуй, например, MD5 или SHA-1. Не забывай, что хэши разных последовательностей теоретически могут совпадать.

Числа больше байта, но, думаю, меньше слова.
Основная задача - отлавливать ошибочные последовательности, сравнивая с эталонными.
Например, эталонная - 1,35,0,0,454,0,1. А последовательность 1,35,0,454,0,0,1 должна дать другую контрольную сумму/хэш/т.д.
mrFatCat
26 августа 2016, 15:21

Constantin написал: контрольную сумму/хэш

Зачем лишние вычисления? Сравнить строки.
Dead Knight
26 августа 2016, 17:16
Вообще, для начала, о чем идет речь? Можно нормальную постановку задачи?

одно дело искать повтрояюшиеся последовательности в конечной/бесконечной строке, второе сравнивать строки определяя, насколько сильно они различаются.
Mx
27 августа 2016, 08:29

Constantin написал: Нужны именно контрольные суммы или хэш. Они потом будут передаваться дальше, для другой обработки и контроля.

Простейший хэш или контрольную суммы можно задать с помощью операции исключительного (XOR). Например завести переменную размером с двойное слово и xorом добавить в неё все последовательные пары элементов ((1,2), (3,4), (5,6), ...).

Constantin написал: Последовательности небольшие (до 200 чисел), но одинаковые на момент проверки.

Я не зря спросил чем не устраивает самый простой алгоритм поэлементного сравнения. Сравнить 200 пар чисел это - достаточно лёгкая операция. Вполне возможно что ничего не надо оптимизировать, а может быть даже и вредно.
Constantin
28 августа 2016, 01:05

Mx написал: Я не зря спросил чем не устраивает самый простой алгоритм поэлементного сравнения. Сравнить 200 пар чисел это - достаточно лёгкая операция. Вполне возможно что ничего не надо оптимизировать, а может быть даже и вредно.

Задача, грубо говоря, связать число из последовательности с его (числом) порядковым номером.
Например:
1 - 2
2 - 25
3 - 0
4 - 132
и
1 - 2
2 - 0
3 - 25
4 - 132
- разные последовательности.
Сейчас используется формула "сумма произведений", т.е. складываются произведения чисел и их порядковых номеров. Но я не уверен, что эта формула дает достаточную точность.
Anton
28 августа 2016, 15:37
Нужно еще понимать, а как может измениться последовательность.
К примеру метод

Mx написал: завести переменную размером с двойное слово и xorом добавить в неё все последовательные пары элементов ((1,2), (3,4), (5,6), ...)

даст возможность заметить изменение единичного бита при передаче (для сохранения результата должны поменяться два бита на одинаковых позициях в разных парах), но не поможет, если изменение - это обмен местами двух элементов на четных позициях последовательности.
От какого рода изменений хочется себя обезопасить по максимуму?
Constantin
28 августа 2016, 22:16

Anton написал: От какого рода изменений хочется себя обезопасить по максимуму?

Обмена элементов не будет, может быть только сдвиг за счет нулей.
Ну, т.е., обмен будет только с соседними нулевыми элементами.
Anton
29 августа 2016, 23:32
Т.е. фактически для проверки идентичности тебе будет достаточно того факта, что нулевые элементы находятся на тех же местах? Тогда заменяешь ненулевые на единицы, из последовательности в 200 чисел получаешь одно 200-битное число, которое в рамках задачи однозначно идентифицирует последовательность (можно меньше 200, учитывая, что число нулей и единиц постоянно, но уже заморочено получится). Дальше работаешь уже с такими числами либо напрямую, либо, если хочется покороче, уже от него брать какой-либо короткий хэш, число коллизий должно быть меньше, чем от хеша исходной последовательности.
Constantin
30 августа 2016, 06:45

Anton написал: Тогда заменяешь ненулевые на единицы, из последовательности в 200 чисел получаешь одно 200-битное число, которое в рамках задачи однозначно идентифицирует последовательность

О, это то, что надо, спасибо!
Эта версия форума - с пониженной функциональностью. Для просмотра полной версии со всеми функциями, форматированием, картинками и т. п. нажмите сюда.
Invision Power Board © 2001-2017 Invision Power Services, Inc.
модификация - Яро & Серёга
Хостинг от «Зенон»Сервера компании «ETegro»