Форумы портала PHP.SU » » Хранение данных, их вывод и обработка » Уникальный id для комбинации чисел

Страниц (1): [1]
 

1. pps88 - 21 Октября, 2017 - 17:41:03 - перейти к сообщению
Доброго времени суток.
Ситуация следующая: есть числа от 1 до 1000. Все эти числа могут образовывать 2-х и 3-х значные уникальные комбинации, например 1-2, 2-1, 5-87, 1-2-3, 2-3-1, 47-21-93 и т.д. Но одно и тоже число может встречаться всего один раз в комбинации.
Нужно получить некий id каждой комбинации, который не будет зависеть от перестановки числ комбинации местами: id для 1-2-3 будет равным id для 3-2-1 или 2-3-1

Будет использоваться примерно так: получаем случайную комбинацию из 2-х или 3-х не повторяющихся цифр, например 57.
Дополнительно имеем массив id из "подходящих" комбинаций созданных сторонним приложением. Получаем id для 57 и циклом перебирая сторонний массив и ищем в нем наш id.

Всем заранее спасибо!
2. LIME - 21 Октября, 2017 - 19:45:50 - перейти к сообщению
не совсем понял задачу
возможно поможет сортировка комбинации по возрастанию с удалением дублей
если массив получится большой и поиск будет производится неоднократно - сортировка массива по возрастанию комбинаций и бинарный поиск(гуглить)
возможно
3. dcc0 - 23 Октября, 2017 - 22:10:50 - перейти к сообщению
В одном массиве id уникальны.
Последняя фраза: берем id одного массива и смотрим в другом элемент по этому id?
4. Строитель - 23 Октября, 2017 - 23:10:01 - перейти к сообщению
LIME пишет:
бинарный поиск
Спасибо )
5. pps88 - 29 Октября, 2017 - 10:37:24 - перейти к сообщению
Спасибо всем за советы.
По факту решил пойти ранее известным и протоптанным путем: сортировка комбинации чисел по возрастанию и получение md5 hash. hash и ищется в стороннем массиве.
Бинарный поиск показался громоздким, либо мне попадались такие его реализации.
6. LIME - 29 Октября, 2017 - 10:43:44 - перейти к сообщению
хэш тут не нужен
достаточно склеить через разделитель
если уж непременно хочется хэш тогда лучше http://php.net/manual/ru/function.crc32.php
он более быстрый но не криптографический а тут это и не надо
(Добавление)
ну и коллизии теоретически возможны
7. Мелкий - 29 Октября, 2017 - 12:32:20 - перейти к сообщению
Бинарный поиск здесь не нужен потому что бинарным поиском искать по хеш-таблице с двусвязным списком штука довольно странная. А массивы php именно являются хеш-таблицей совмещённой с двусвязным списком.

Ну а раз хэш-таблица уже есть - то почему бы ей и не воспользоваться.

pps88 пишет:
не будет зависеть от перестановки числ комбинации местами: id для 1-2-3 будет равным id для 3-2-1 или 2-3-1

Собственно всё что нужно для удовлетворения вот этому условию - отсортировать входящие ключи хоть по возрастанию, хоть по убыванию.
А затем склеить через разделитель в строку, утрамбовать в int (int32 вполне хватает для хранения 3 чисел 0-999 (константное смещение -1 от требуемого по задаче диапазона)) или просто разложить в многомерный массив как есть.
8. LIME - 29 Октября, 2017 - 12:44:24 - перейти к сообщению
Мелкий пишет:
Бинарный поиск здесь не нужен потому что бинарным поиском искать по хеш-таблице с двусвязным списком штука довольно странная.
я понял что нужен поиск не по ассоциативному массиву, а по обычному по значениям. Хотя если уж сортировать то можно и ассоциативный слепить. Вобщем как я говорил я вообще не понял задачу. И сейчас не понимаю.
9. Мелкий - 29 Октября, 2017 - 13:23:16 - перейти к сообщению
LIME пишет:
а по обычному по значениям

А разница? Хотя, помнится, на уровне zend'а числовые и ассоциативные всё-таки слегка различаются. Не помню деталей.
Можно со ссылками на https://github[dot]com/php/php-src
10. LIME - 29 Октября, 2017 - 13:40:02 - перейти к сообщению
Мелкий пишет:
А разница?

PHP:
скопировать код в буфер обмена
  1. $arr = [1785, 234, 763... 7999];
найди входит ли в массив значение 91919
каким образом тут может быть использована хэш-таблица?
11. Мелкий - 29 Октября, 2017 - 15:24:18 - перейти к сообщению
LIME пишет:
каким образом тут может быть использована хэш-таблица?

А бинарный поиск? Множество-то не отсортировано.
Ну так если всё равно препроцессить данные - то загнать значения в ключи другого массива. Поиск существования ключа в php-массиве === поиск по хеш-таблице.
12. LIME - 29 Октября, 2017 - 15:28:02 - перейти к сообщению
LIME пишет:
сортировка массива по возрастанию комбинаций и бинарный поиск
LIME пишет:
Хотя если уж сортировать то можно и ассоциативный слепить.
в хэш-таблице есть свои минусы
и надо смотреть как массив устроен
но это уже совсем другая история
13. Мелкий - 29 Октября, 2017 - 16:08:04 - перейти к сообщению
LIME пишет:
и надо смотреть как массив устроен

О чём я и говорю, собственно. Если есть массив - значит уже есть хеш-таблица и двусвязный список (вот старая статья nikic, про изменения в php7 искать лениво). Пытаться делать руками бинарный поиск поверх уже имеющейся хеш-таблицы - штука загадочная и на пустом месте требующая лишних вычислительных телодвижений и куда больше кода.
14. LIME - 29 Октября, 2017 - 16:13:01 - перейти к сообщению
Мелкий пишет:
Пытаться делать руками бинарный поиск поверх уже имеющейся хеш-таблицы
это если лист есть хэш-таблица
не удивлюсь если в 7 это правильный массив ссылок на значения
можно конечно не сортировать а перевернуть в хэш-таблицу
тогда много всего можно учитывать
(Добавление)
нет
проверил
добавлял с целочисленными ключами произвольно
порядок добавления сохранился

 

Powered by ExBB FM 1.0 RC1