PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


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

> Без описания
pps88
Отправлено: 21 Октября, 2017 - 17:41:03
Post Id



Новичок


Покинул форум
Сообщений всего: 60
Дата рег-ции: Май 2015  


Помог: 0 раз(а)




Доброго времени суток.
Ситуация следующая: есть числа от 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.

Всем заранее спасибо!

(Отредактировано автором: 21 Октября, 2017 - 18:02:15)

 
 Top
LIME
Отправлено: 21 Октября, 2017 - 19:45:50
Post Id



Активный участник


Покинул форум
Сообщений всего: 9990
Дата рег-ции: Нояб. 2010  


Помог: 296 раз(а)




не совсем понял задачу
возможно поможет сортировка комбинации по возрастанию с удалением дублей
если массив получится большой и поиск будет производится неоднократно - сортировка массива по возрастанию комбинаций и бинарный поиск(гуглить)
возможно

(Отредактировано автором: 21 Октября, 2017 - 21:29:33)



-----
вау
я кажется понял жастЮзера!!!
 
 Top
dcc0
Отправлено: 23 Октября, 2017 - 22:10:50
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 985
Дата рег-ции: Июль 2014  


Помог: 7 раз(а)




В одном массиве id уникальны.
Последняя фраза: берем id одного массива и смотрим в другом элемент по этому id?
 
 Top
Строитель
Отправлено: 23 Октября, 2017 - 23:10:01
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 973
Дата рег-ции: Февр. 2014  


Помог: 33 раз(а)




LIME пишет:
бинарный поиск
Спасибо )
 
 Top
pps88
Отправлено: 29 Октября, 2017 - 10:37:24
Post Id



Новичок


Покинул форум
Сообщений всего: 60
Дата рег-ции: Май 2015  


Помог: 0 раз(а)




Спасибо всем за советы.
По факту решил пойти ранее известным и протоптанным путем: сортировка комбинации чисел по возрастанию и получение md5 hash. hash и ищется в стороннем массиве.
Бинарный поиск показался громоздким, либо мне попадались такие его реализации.
 
 Top
LIME
Отправлено: 29 Октября, 2017 - 10:43:44
Post Id



Активный участник


Покинул форум
Сообщений всего: 9990
Дата рег-ции: Нояб. 2010  


Помог: 296 раз(а)




хэш тут не нужен
достаточно склеить через разделитель
если уж непременно хочется хэш тогда лучше http://php.net/manual/ru/function.crc32.php
он более быстрый но не криптографический а тут это и не надо
(Добавление)
ну и коллизии теоретически возможны


-----
вау
я кажется понял жастЮзера!!!
 
 Top
Мелкий Супермодератор
Отправлено: 29 Октября, 2017 - 12:32:20
Post Id



Активный участник


Покинул форум
Сообщений всего: 11592
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 564 раз(а)




Бинарный поиск здесь не нужен потому что бинарным поиском искать по хеш-таблице с двусвязным списком штука довольно странная. А массивы php именно являются хеш-таблицей совмещённой с двусвязным списком.

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

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

Собственно всё что нужно для удовлетворения вот этому условию - отсортировать входящие ключи хоть по возрастанию, хоть по убыванию.
А затем склеить через разделитель в строку, утрамбовать в int (int32 вполне хватает для хранения 3 чисел 0-999 (константное смещение -1 от требуемого по задаче диапазона)) или просто разложить в многомерный массив как есть.


-----
PostgreSQL DBA
 
 Top
LIME
Отправлено: 29 Октября, 2017 - 12:44:24
Post Id



Активный участник


Покинул форум
Сообщений всего: 9990
Дата рег-ции: Нояб. 2010  


Помог: 296 раз(а)




Мелкий пишет:
Бинарный поиск здесь не нужен потому что бинарным поиском искать по хеш-таблице с двусвязным списком штука довольно странная.
я понял что нужен поиск не по ассоциативному массиву, а по обычному по значениям. Хотя если уж сортировать то можно и ассоциативный слепить. Вобщем как я говорил я вообще не понял задачу. И сейчас не понимаю.


-----
вау
я кажется понял жастЮзера!!!
 
 Top
Мелкий Супермодератор
Отправлено: 29 Октября, 2017 - 13:23:16
Post Id



Активный участник


Покинул форум
Сообщений всего: 11592
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 564 раз(а)




LIME пишет:
а по обычному по значениям

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


-----
PostgreSQL DBA
 
 Top
LIME
Отправлено: 29 Октября, 2017 - 13:40:02
Post Id



Активный участник


Покинул форум
Сообщений всего: 9990
Дата рег-ции: Нояб. 2010  


Помог: 296 раз(а)




Мелкий пишет:
А разница?

PHP:
скопировать код в буфер обмена
  1. $arr = [1785, 234, 763... 7999];
найди входит ли в массив значение 91919
каким образом тут может быть использована хэш-таблица?

(Отредактировано автором: 29 Октября, 2017 - 13:49:26)



-----
вау
я кажется понял жастЮзера!!!
 
 Top
Мелкий Супермодератор
Отправлено: 29 Октября, 2017 - 15:24:18
Post Id



Активный участник


Покинул форум
Сообщений всего: 11592
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 564 раз(а)




LIME пишет:
каким образом тут может быть использована хэш-таблица?

А бинарный поиск? Множество-то не отсортировано.
Ну так если всё равно препроцессить данные - то загнать значения в ключи другого массива. Поиск существования ключа в php-массиве === поиск по хеш-таблице.


-----
PostgreSQL DBA
 
 Top
LIME
Отправлено: 29 Октября, 2017 - 15:28:02
Post Id



Активный участник


Покинул форум
Сообщений всего: 9990
Дата рег-ции: Нояб. 2010  


Помог: 296 раз(а)




LIME пишет:
сортировка массива по возрастанию комбинаций и бинарный поиск
LIME пишет:
Хотя если уж сортировать то можно и ассоциативный слепить.
в хэш-таблице есть свои минусы
и надо смотреть как массив устроен
но это уже совсем другая история


-----
вау
я кажется понял жастЮзера!!!
 
 Top
Мелкий Супермодератор
Отправлено: 29 Октября, 2017 - 16:08:04
Post Id



Активный участник


Покинул форум
Сообщений всего: 11592
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 564 раз(а)




LIME пишет:
и надо смотреть как массив устроен

О чём я и говорю, собственно. Если есть массив - значит уже есть хеш-таблица и двусвязный список (вот старая статья nikic, про изменения в php7 искать лениво). Пытаться делать руками бинарный поиск поверх уже имеющейся хеш-таблицы - штука загадочная и на пустом месте требующая лишних вычислительных телодвижений и куда больше кода.


-----
PostgreSQL DBA
 
 Top
LIME
Отправлено: 29 Октября, 2017 - 16:13:01
Post Id



Активный участник


Покинул форум
Сообщений всего: 9990
Дата рег-ции: Нояб. 2010  


Помог: 296 раз(а)




Мелкий пишет:
Пытаться делать руками бинарный поиск поверх уже имеющейся хеш-таблицы
это если лист есть хэш-таблица
не удивлюсь если в 7 это правильный массив ссылок на значения
можно конечно не сортировать а перевернуть в хэш-таблицу
тогда много всего можно учитывать
(Добавление)
нет
проверил
добавлял с целочисленными ключами произвольно
порядок добавления сохранился


-----
вау
я кажется понял жастЮзера!!!
 
 Top
Страниц (1): [1]
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« Хранение данных, их вывод и обработка »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB