VN
Log n
У соответствия сложность О(1)
Size: a a a
2020 January 15
YH
Vassily Poupkine
Через Найти()?
Не, через найти там обход и в худшем n будет
VN
Vassily Poupkine
Я так понял выше топят за массив только если ключ полностью подходит как индекс массива (т.е. число + сплошная нумерация с нуля)
Правильно.
А в общем случае нужно дополнительно в соответствии держать значение и его индекс.... Чтобы быстро найти по индексу??? ((((
А в общем случае нужно дополнительно в соответствии держать значение и его индекс.... Чтобы быстро найти по индексу??? ((((
VP
Не, через найти там обход и в худшем n будет
А как тогда предлагаешь "проверить массив на наличие объекта"?
YH
Vassily Poupkine
А как тогда предлагаешь "проверить массив на наличие объекта"?
VN
Задача: исключить повторяющиеся элементы массива при решении с помощью массивов имеет сложность n в квадрате.
Когда такое попадается в коде с 10000 элементами, то ускорение при оптимизации равно в 10000 раз. И программисты потом открывают рты(
Когда такое попадается в коде с 10000 элементами, то ускорение при оптимизации равно в 10000 раз. И программисты потом открывают рты(
VP
Как отсортировать / разделить массив "на половины" если у нас он состоит из ссылок на объекты БД?
YH
Vassily Poupkine
Как отсортировать / разделить массив "на половины" если у нас он состоит из ссылок на объекты БД?
Btw ссылки можно сравнивать с кода 1с (больше, меньше)?
ПЗ
Vladimir Nadulich
- ну это мы говорим о ресурсности самих объектов языка, а не какую скорость конкретных алгоритмов они обеспечивают. Это как говорить, что лопата всегда лучше грабель, не понимая какую задачу мы решаем. Лопата проще и точка. Нужна всегда лопата. А прозвучало это именно так ((
- вставка в соотвествие? хммм... вот тут услышать бы мнение из разных языков. Реально хз как в 1С, но если бы было так - это была бы жопа и добавление N млн элементов в массив и в соотв отличалось бы пропорционально количеству элементов раз. А такого точно нет. Ключи в соотвествие добавляются то ли в в конец, то ли в свободное место, то ли в отдельный адрес... Они же не упорядочены... Зачем поиск/вставки?
- всему свое место. Например, все кэши делаются на парах К-З. Получение Значения Ключа мгновенное из любого объема, не зависит от размера словаря, и это главное. Массив тут никак не применишь.
- вставка в соотвествие? хммм... вот тут услышать бы мнение из разных языков. Реально хз как в 1С, но если бы было так - это была бы жопа и добавление N млн элементов в массив и в соотв отличалось бы пропорционально количеству элементов раз. А такого точно нет. Ключи в соотвествие добавляются то ли в в конец, то ли в свободное место, то ли в отдельный адрес... Они же не упорядочены... Зачем поиск/вставки?
- всему свое место. Например, все кэши делаются на парах К-З. Получение Значения Ключа мгновенное из любого объема, не зависит от размера словаря, и это главное. Массив тут никак не применишь.
https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0
Пруфа нет, но по декларируемым свойствам Соответствие это хешмеп
Пруфа нет, но по декларируемым свойствам Соответствие это хешмеп
VN
https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0
Пруфа нет, но по декларируемым свойствам Соответствие это хешмеп
Пруфа нет, но по декларируемым свойствам Соответствие это хешмеп
В питоне это так
ВМ
Может я чего пропустил, но как имея только значение проверить его уникальность в соответствии? (Т.е. когда ключ не известен)?
Ведь именно в этом спор.
Имея значение массива, проверка наличия его в массиве это перебор циклом.
А в соответствии как проверять? Не циклом разве?
Ведь именно в этом спор.
Имея значение массива, проверка наличия его в массиве это перебор циклом.
А в соответствии как проверять? Не циклом разве?
ПЗ
Так оно для этого и не подходит
VP
Может я чего пропустил, но как имея только значение проверить его уникальность в соответствии? (Т.е. когда ключ не известен)?
Ведь именно в этом спор.
Имея значение массива, проверка наличия его в массиве это перебор циклом.
А в соответствии как проверять? Не циклом разве?
Ведь именно в этом спор.
Имея значение массива, проверка наличия его в массиве это перебор циклом.
А в соответствии как проверять? Не циклом разве?
В соответствии будут только ключи - сами элементы. Через метод "Получить()" проверяется, есть ли там такой элемент или нет
ПЗ
По ключу - пожалуйста.
По значению разве что ТабЗнач индексированная на ум приходит.
Но я бы бы пожалуй остановился, подумал бы и поглядел на алгоритм.
По значению разве что ТабЗнач индексированная на ум приходит.
Но я бы бы пожалуй остановился, подумал бы и поглядел на алгоритм.
ПЗ
Хотя помню, пару раз приходилось делать пару соответствий, инвертированных. Т.е. условно в одном К/З - Индекс/Ссылка, во втором - Ссылка/Индекс. Так можно быстро и легко гонять в обе стороны.
Но память и время выполнения страдают, конечно. В той ситуации было допустимо.
Но память и время выполнения страдают, конечно. В той ситуации было допустимо.
VN
Спасибо. Может хоть итс каким-то авторитетым словом будет
VN
По ключу - пожалуйста.
По значению разве что ТабЗнач индексированная на ум приходит.
Но я бы бы пожалуй остановился, подумал бы и поглядел на алгоритм.
По значению разве что ТабЗнач индексированная на ум приходит.
Но я бы бы пожалуй остановился, подумал бы и поглядел на алгоритм.
Зная что нужно будет контролироватьпихать контролируемые значения в КЗ.Значение - верх слабоумия. Не находите?
Но если вдруг у вас уж так сложилось, то сначала формируется соответствие к ключами, линейно, за один проход. А потом без квадратичных сложностей выполняются сами контроли.
PS: Впрочем чем медленнее работают алгоритмы, тем больше у меня работы. )
Но если вдруг у вас уж так сложилось, то сначала формируется соответствие к ключами, линейно, за один проход. А потом без квадратичных сложностей выполняются сами контроли.
PS: Впрочем чем медленнее работают алгоритмы, тем больше у меня работы. )
ВМ
Т.е. что бы соответствие в поиске по значению имело преимущество перед массивом - значения надо записывать в ключи?
VP
Т.е. что бы соответствие в поиске по значению имело преимущество перед массивом - значения надо записывать в ключи?
А как ты по-другому сделаешь поиск в соответствии? Остается только перебор "Для каждого из", что очевидно сюр.