Python / Говнокод #26782 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
import json
a = {}
b = {}
for i in xrange(128): a[str(i)] = i
for i in a: b[i] = a[i]
print a == b
print json.dumps(a) == json.dumps(b)

Результат:
True
False

Почему не True True ?

Запостил: a02810 a02810, (Updated )

Комментарии (145) RSS

  • потому что
    а) питух дерьмо
    б) for i in xrange и i in a не гарантируют одинаковый порядок ключей
    в) на сравнение словарей это влияет, а вот на сравнение строк еще как
    г) возвращаемся к тому, что питух дерьмо, ибо мапа не должна зависеть от порядка объявления ключей
    д) сам-то принт чего не сделаешь да не посмотришь
    Ответить
  • Потому что выкинь двойку же, её даже официально уже полгода как закопали. В 3.7 порядок ключей в словарях строго сохраняется.
    Ответить
    • > порядок ключей сохраняется

      Лучше бы отсортировали по алфавиту. Кому нахуй нужен этот порядок добавления?

      Я вот в другом порядке вторую мапу набью. И она будет равна первой т.к. при сравнении порядок не играет роли. А json представление у них будет разное т.к. порядок обхода разный. Т.е. тройка не решает эту проблему.

      З.Ы. А решить эту проблему можно только сортировкой перед сериализацией в жсон. Почти как DER в ASN.1
      Ответить
      • > Т.е. тройка не решает эту проблему.
        Какую проблему-то? В «Питоне» «JSON» — это просто строка, о её внутренностях «Питон» ничего не знает и знать не должен. Никакой проблемы в этом нет.
        Вот если бы он словари сравнивал порядкозависимо, тогда да, был бы багор.
        Ответить
        • Проблему того, что сериализация словаря в JSON идёт без предварительной сортировки ключей. Из-за этого равные словари могут иметь разную сериализацию.

          Т.е. в терминах ASN.1 это аналог BER но не DER.
          Ответить
          • > предварительной сортировки ключей
            - зачем? зачем?
            Ответить
            • Чтобы как в DER или тех же торрентах получалось единственное представление.

              Хотя, в json, конечно, из-за пробелов и переносов строк все полимеры будут просраны. Всё-таки в двоичных форматах единства представления легче добиться.
              Ответить
              • Так а какой смысл в этом? На клиенте ты всё равно преобразовываешь JSON в какие-то местные словарные типы данных, сортировка скорее всего собьётся при трансформации.

                Чисто для сравнения двух джейсонов?
                Ответить
              • > Хотя, в json, конечно, из-за пробелов и переносов строк все полимеры будут просраны.
                Это-то как раз не проблема, достаточно просто не ставить никакие пробелы и переносы строк. А вот что меня беспокоит — так это представление плавающих питухов. Можно ли гарантировать, что один и тот же питух будет сериализован в одну и ту же строку на любом компьютере?
                Ответить
                  • А это очень сложно проверить. На свежих сборках под интел всё скорее всего совпадёт.

                    Надо тестить старые сборки питона или сборки под другие платформы. Вот там могут быть отличия.
                    Ответить
                    • А, так вопрос про разные версии Пистона?

                      Я думал, надо проверять разные языки и сериализаторы
                      Ответить
                    • Так надо не только «Питон», надо и все остальные сериализаторы проверять.
                      Ответить
                      • Где-то была кстати статья про анализ жсон парсеров и генераторов. И там в конце был вывод, что всё хуёво, формат недоспецифирован и они все в каких-то мелочах отличаются, местами даже несовместимы.
                        Ответить
                  • Чтобы это проверить, нужно будет каждого питуха сериализовать на каждом существующем компьютере.
                    На своём проверил, осталось проверить все остальные:
                    >>> petuh = 80.58545612549864
                    >>> json.dumps(petuh)
                    '80.58545612549864'
                    Ответить
                    • > все остальные

                      Для всех остальных чисел. А то вдруг ты просто удачное число выбрал.
                      Ответить
                    • let encoder = JSONEncoder()
                      let petuh = 80.58545612549864
                      let data = try! encoder.encode(petuh)
                      let string = String(data: data, encoding: .utf8)!
                      print(string)

                      -
                      80.585456125498638


                      Какой багор)))
                      Ответить
                        • Я не понимаю, как они добились такого результата.

                          Если сделать из дабла строку при помощи интерполяции, то там всё будет окей.
                          Ответить
                      • Ну и с PHP точно не сойдётся т.к. там корректировка LSB для красивых результатов. PHP никогда не выводит 0.30000000001 и 0.29999999999
                        Ответить
                        • Почему нельзя представлять плавучку в JSON точь-в-точь так, как она описана в памяти?

                          А как ее всякие говны выводят -- пофиг же
                          Ответить
                          • А вдруг там индеец не того направления, к которому ты привык
                            Ответить
                            • Для этого есть htonы всякие.
                              Достаточно сказать "в кроссплатформенном формате JSON индеец имеет такое вот направление"
                              Ответить
                              • Во-первых, это всё же будет не совсем так, как она описана в памяти.

                                Во-вторых, JSON это человекочитаемый формат.

                                Потому сериализовывать нужно в простые дроби.
                                Ответить
                                • Не совсем так, да. Но будет легкий способ его преобразовать.

                                  >человекочитаемый
                                  а, ну тогда вам шашечки, или ехать?
                                  Или у нас человекочитаемый формат, или ieee-754.

                                  Имхо, для передачи данных между программами человекочитаемый формат не нужен.
                                  Ответить
                                  • Да ну ладно.

                                    Осилили же как-то printf'ы и прочие логи с выводом плавучки без потери точности.
                                    Ответить
                                    • А где гарантия, что кто-то распарсит мои логи, и построит точно такую же плавучку?
                                      Ответить
                                      • Ну мы ж пока вроде про сериализацию.

                                        Десериализация в следующем номере или по короткому номеру
                                        Ответить
                                        • Есть две задачи:

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

                                          Человек -- существо слабое, и нет большой беды в том, что часть точности питуха проебется.
                                          Тут можно сделать printf из любого практически языка программирования.

                                          Компьютеру же хочется получить питуха точь-в-точь таким, каким его закодировали на той стороне (разумеется, если софт и хард поддерживают питухов такого размера).

                                          Обидно будет узнать, что я передал сообщение по цепочке от компа A к компу B, а оттуда к компу C, и с каждым шагом в нем менялся питух.

                                          Это как с аналоговой пленочной аудиокассетой: чем больше раз переписал песню -- тем она хуёвее.

                                          Так быть не должно.

                                          К сожалению, нужный компьютеру питух человеку не читаем.

                                          Потому можно ввести два вида питуха:

                                          unskillable-petuh: для человека
                                          tsar-petuh aka strict-petuh: для компа. В Hex.
                                          Ответить
                                      • Почему же? Если в двоичном питухе в экспоненциальной форме выводить, почему нет?
                                        Ответить
                                        • Да даже в десятичном можно походу. В десятке есть 2, поэтому двоичную дробь таки можно записать как десятичную. Проблемы начинаются только в обратную сторону, когда какое-нибудь 0.1 пытаешься записать как двоичную дробь.
                                          Ответить
                                      • То есть возможны варианты, что я заассайню во флоат compile-time литерал, а потом выведу его на экран и получу неожиданность?
                                        Ответить
                                        • Ну да. Он испортится в момент его преобразования из твоего текста в дабл. Выведется то он уже без потерь, но может не совпасть с тем, что ты писал.

                                          Типа пишешь 0.1 а получаешь 0.99999999 или 0.100000001. Потому что между ними более подходящих чисел во флоате нет.
                                          Ответить
                                          • Я надеюсь, что там всё же подразумевалось 0.09999999, а то мне совсем страшно стало!
                                            Ответить
                                              • Ну и вывод без потерь потребует N десятичных разрядов на N двоичных. Т.е. если у нас там мантисса на 52 бита, то надо будет в десятичке 52 цифры высрать. А столько цифр по-моему ни одна либа не выводит.
                                                Ответить
                                                • В это я не въехал, к сожалению.

                                                  Если у нас мантисса на 4 бита, то туда поместится 16 значений, а это всего два порядка в десятичной.

                                                  Но у меня с переводами между системами немного всё проржавело, могу и хуйню написать ненароком.
                                                  Ответить
                                                  • Жопа в том, что эти 4 бита представляют, к примеру, 0.5, 0.25, 0.125 и 0.0625. И если ты теперь из них будешь составлять число, то у тебя получится 4 значащих цифры.

                                                    З.Ы. Хотя, наверное, можно округлить в нужную сторону чтобы потом при обратном преобразовании звёзды сошлись... Но это уже не "без потерь", а просто "обратимо несмотря на погрешность".
                                                    Ответить
                                                    • Куик, а почему нельзя представить 4 бита как десятичное число, как делают например в IP адресах?

                                                      1111 -- 15

                                                      Потому, что это будет так же нечитаемо, как 0xF?
                                                      Ответить
                                                      • Потому что это уже дробь с основанием 2^N, непривычная человеку. Как в примере про 1609/512.
                                                        Ответить
                                                        • В общем единственный способ усидеть на двух стульях, и сделать питуха одновременно И человекочитаемым И без потери точности, это сделать его длиннющим, да?
                                                          Ответить
                                                  • Ну т.е. возьмём например двоичные дроби 0.101(2), 0.110 (2) и 0.111 (2).

                                                    Реально без потерь они означают 0.625, 0.750 и 0.875.

                                                    Но у нас битов даже на один десятичный разряд не набирается, поэтому мы смело можем их округлить до 0.6, 0.8 и 0.9. Ну и когда мы будем их переводить обратно в двоичное, то получим то что и было на входе.

                                                    Т.е. вроде и обратимо, но 0.101 (2) это нихуя не 0.6. Хотя и рядом.

                                                    Видимо вот такой приём и подразумевается как "вывод без потерь точности".
                                                    Ответить
                                  • > простые дроби

                                    Ну или двоичные дроби. Впрочем ни то ни другое неюзабельно для человека.

                                    Вот будет там какое-нибудь 1609/512 и ты даже не подумаешь, что это кусок пи.
                                    Ответить
                                    • Тут вопрос в том, нужно ли мне знать, что это Пи.

                                      И Пи я узнаю из 3.14блабла, да. А вот там какую-нибудь постоянную Планка уже фиг, а потому какая мне разница, какая там дробь?
                                      Ответить
                          • В виде десятичной дроби её ма-те-ма-ти-чес-ки невозможно вывести. Придётся прям двоичное представление вываливать хексами, а это нечитаемо.
                            Ответить
    • Минимальный пример, который на 3.8 выдаёт True False:
      a = {1:2, 2:3}
      b = {2:3, 1:2}
      print(a == b)
      print(json.dumps(a) == json.dumps(b))
      Ответить
        • А нахуй он нужен?

          Именно поэтому я за кресты, где всё просто и понятно: есть отсортированная мапа и есть неотсортированная мапа, в обоих случаях всем похуй на порядок добавления.

          З.Ы. В питоне отсортированной мапы, кстати, нету.
          Ответить
          • А нахуй нужна отсортированная мапа, если есть словарь с сохранением порядка ключей?

            {str(x): x for x in sorted([5, 1, 4, 3, 2])}
            {'1': 1, '2': 2, '3': 3, '4': 4, '5': 5}
            Ответить
            • А если я что-то добавлю, то этот словарь перестанет быть отсортированным. И мне в каждой точке, где важна сортировка, придётся её сортировать заново (например во время сериализации). С тем же успехом я и неотсортированную мапу юзать могу сортируя ключи во время сериализации. В чём польза от порядка вставки?
              Ответить
              • Именно поэтому я за «иммутабельность».
                В «PEP 468» это сделали для того, чтобы сохранить порядок аргументов в **kwargs: https://www.python.org/dev/peps/pep-0468/#id6.

                А вообще, «dict» — это хэш-массив, его ключи совершенно не обязаны быть сравнимыми/сортируемыми.
                Ответить
                • А зачем мне порядок аргументов в kwargs? Я же их по имени юзаю.
                  Ответить
                    • Да просто у других скриптушков порядок сохранялся, вот питонятам и завидно стало. Никакой особой логики или пользы в этом нет.
                      Ответить
                        • В жс вроде как раз перед питоном такую гарантию дали?

                          В пхп вроде тоже есть.
                          Ответить
                          • да, в JS кажется что есть, но не без ануса
                            > let a = {};
                            undefined
                            > a[100] = 'a';
                            'a'
                            > a['a'] = 'a';
                            'a'
                            > a[10] = 'a';
                            'a'
                            > a
                            { '10': 'a', '100': 'a', a: 'a' }
                            > Object.keys(a);
                            [ '10', '100', 'a' ]
                            >


                            First, the keys that are integer indices (what these are is explained later), in ascending numeric order.

                            Then, all other string keys, in the order in which they were added to the object.

                            Lastly, all symbol keys, in the order in which they were added to the object.



                            про пых не зна
                            Ответить
                              • Это такой специальный уникальный объект, который никогда не равен никакому другому. «Никогда», правда, в стиле «JS»: никогда, но иногда можно.
                                https://govnokod.ru/26415#comment524714
                                Ответить
                                • Процитирую оттуда смешной багор:
                                  В «MDN» эпический багор есть:
                                  >>> In contrast to Symbol(), the Symbol.for() function creates a symbol available
                                      in a global symbol registry list.
                                  >>> The global symbol registry is a list with the following record structure and
                                      it is initialized empty
                                  >>> To avoid name clashes with your global symbol keys and other (library code)
                                      global symbols, it might be a good idea to prefix your symbols:
                                  >>> Symbol.for('mdn.foo');
                                  >>> Symbol.for('mdn.bar');
                                  
                                  Это же та самая херня, которую скучные дяди с галстуками в своих коболах решали с
                                  середины прошлого века: глобальные имена, глобальные имена с ручными
                                  префиксами, пространства имён, локальные имена, замыкания… Джаваскриптовые
                                  хипстеры как всегда решительно встали в самое начало пути изобретения колеса.
                                  Ответить
                              • Это как atom или как symbol в ruby.

                                Строка, введенная пользователем, равна другой строке, введеной пользователем. А символ не равен
                                Ответить
                          • ps:
                            фу! руби!
                            https://ruby-doc.org/core-2.7.0/Hash.html

                            Hashes enumerate their values in the order that the corresponding keys were inserted.

                            Пишут, что since 1.9.

                            Кто вообще еще не гарантирует это говно из скриптоговна? lua и perl?
                            Ответить
                  • The cases where it would be highly desirable to be able use keyword
                    arguments to control the order of display of a collection of key
                    value pairs are ones like:
                    
                    * printing out key:value pairs in CLI output
                    * mapping semantic names to column order in a CSV
                    * serialising attributes and elements in particular orders in XML
                    * serialising map keys in particular orders in human readable formats
                      like JSON and YAML (particularly when they're going to be placed
                      under source control)
                      
                      
                    Other Use Cases
                    
                    Mock objects.
                    Controlling object presentation.
                    Alternate namedtuple() where defaults can be specified.
                    Specifying argument priority by order.
                    Ответить
                    • >* printing out key:value pairs in CLI output
                      то-есть если я сортирну их явно перед выводом, то все будет тормозить?
                      не надо только мне рассказывать, что они не сравниваемые: печатаются строки, а строки можно сравнивать.

                      >* mapping semantic names to column order in a CSV
                      эм.. типа поменял сигнатуру функции, и поменялся аутпут?

                      >>* serialising attributes and elements in particular orders in XML
                      Это единственное, что ладно. Но почему тогда явно не заказать ordereddict?

                      >Mock objects.
                      >Alternate namedtuple() where defaults can be specified.
                      Тим Тоуди, дружище!


                      В общем ладно, похуй.

                      Вряд-ли Insertion order станет боттлнеком в скриптоговне, пусть будет
                      Ответить
                      • > то-есть если я сортирну их явно перед выводом, то все будет тормозить?
                        Так смысл не в том, чтобы их отсортировать, смысл в том, чтобы показать их в том порядке, в каком они были переданы в функцию.

                        > Но почему тогда явно не заказать ordereddict?
                        Потому что тогда тебе придётся вместо простого «f(a=1, b=2, c=3)» писать питушарское «f(OrderedDict((a, 1), (b, 2), (c, 3)))» (не знаю, какой там точно у него коньструктор, мог наврать).

                        Мне, в общем-то, наиболее полезным показался последний пример, с «Specifying argument priority by order».
                        Ответить
                        • >Так смысл не в том, чтобы их отсортировать, смысл в том, чтобы показать их в том порядке, в каком они были переданы в функцию.

                          Мне сложно придумать юзкейс, когда мне это важно, но я могу не уметь мыслить как питониста.

                          >Потому что тогда тебе придётся вместо простого «f(a=1, b=2, c=3)» писать питушарское

                          Почему не сделать это при объвлении?
                          def foo(**kwargs_o):
                               pass


                          >Specifying argument priority by order
                          типа я передал foo и bar, и foo важнее, потому что первый?

                          Мне кажется, что семантика мутновата, хотя может и быть полезно
                          Ответить
                          • > Почему не сделать это при объвлении?
                            «kwargs» — это просто название аргумента, оно может быть любым. То, что в этот аргумент складываются именованные параметры, определяют две звёздочки перед нем. В пепе, в разделе альтернатив, есть предложение расширить синтаксис тремя звёздочками, но это, очевидно, хуёвая идея. «New syntax is only added to Python under the most dire circumstances».
                            Ответить
                            • Не важно как это сделать.

                              Важно, что:
                              * я, как автор функции, прошу питона сохранить порядок
                              * вызывающей стороне пофиг на это
                              Ответить
                              • > прошу питона сохранить порядок
                                Для этого разработчикам «Питона» придётся расширить синтаксис, а это — плохая идея. К расширению синтаксиса следует прибегать только в самых печальных обстоятельствах, когда без этого будет совсем уж говно.
                                Ответить
        • зачем? зачм?
          я за перл: там порядок в хеше не гарантирован никогда)

          вообще есть три кейса
          * сохранять порядок вставки
          * сортировать по ключу
          * не гарантировать порядок

          чем один лучше другого?
          Ответить
          • > зачем? зачм?
            https://www.python.org/dev/peps/pep-0468/#id6

            > есть три кейса
            Два кейса. Сортировать по ключу нельзя, потому что ключи не обязаны быть сравнимыми. Собственно, они не обязаны даже быть одного типа. А между «сохранять порядок вставки» и «не сохранять порядок вставки» выбор, при прочих равных, очевиден: чем меньше в языке неопределённости, тем лучше.
            Ответить
            • В «PHP» есть функция ksort, которая сортирует хэш-мапы по ключу:
              https://www.php.net/manual/ru/function.ksort.php

              Есть даже krsort, которая сортирует по убыванию ключей. И даже есть uksort, которой ты можешь подсунуть свой компаратор:
              https://www.php.net/manual/ru/function.uksort.php

              Именно поэтому я за «PHP».
              Ответить
            • сохранение порядка вставки накладывает ограничение на реализацию, и делает ее более тяжелой: ты не можешь тупо все в дерево сложить

              зачем давать такую гарантию, которая редко кому нужна

              Ты может и для сета хочешь сохранять порядок?
              Ответить
              • Я даже больше скажу: ключи dict'а ты в любом случае не можешь в дерево сложить. dict — это хэш-массив, его ключи не обязаны быть сравнимыми иметь порядок. Собственно, дерево — это питушня: зачем нужны питушарские O(logN) на поиск, когда можно сделать амортизированное царское O(1)?

                А дали такую гарантию после того, как в «CPython» изменили реализацию словаря на такую, которая гарантировала сохранение порядка вставки. И она оказалась быстрее, чем старая.

                > Ты может и для сета хочешь сохранять порядок?
                А такой сет вполне можно эмулировать имеющимся словарём, причём с сохранением всех асимптот.
                Ответить
                • Совершенно не обязательно им сравнимыми между собой. Достаточно уметь брать от них хеш.
                  Хеш, разумеется, может совпадать.
                  Далее, ты пихаешь их в дерево по хешу, за логарифм находишь нужную корзиночку, и все объекты там проверяешь. Правда, перестройка дерева операция не дешевая.

                  >когда можно сделать амортизированное царское O(1)?
                  А как можно получить O(1) для случайного ключа не засрав всю память?

                  >И она оказалась быстрее, чем старая.
                  Кажется, что не всегда)
                  https://bugs.python.org/msg275587
                  Ответить
                  • > Далее, ты пихаешь их в дерево по хешу
                    А зачем? Ты получишь поиск за питушарские O(logN), при этом тебе ещё и хэш нужно вычислять.

                    > А как можно получить O(1) для случайного ключа не засрав всю память?
                    https://en.wikipedia.org/wiki/Hash_table
                    Вкратце: вспоминаем Царя, берём МАССИВ buckets на N элементов-списков, берём нормированный в [0; N) (банальным %, например) хэш H ключа, добавляем в buckets[H] пару (ключ, значение) — как ты и предлагал.
                    Теперь, если у нас достаточно хороший хэш и достаточно малая заполненность таблицы (отношение суммарного количества элементов к N), то в каждой корзине у нас будет по одному элементу и мы получим то самое амортизированное O(1). Это — самая примитивная реализация, в реальности, конечно, всё сложнее (плюс существует второй вореант с «открытой адресацией» — это когда в МАССИВЕ хранятся не списки, а сразу пары (ключ, значение), и если при очередной вставке buckets[H] занята, то мы поочерёдно пытаемся вставить в H+1, H+2, H+3 и так далее, причём вместо простого инкремента могут применяться весьма изощрённые техники).
                    В «Питоне» всё осложняется тем, что нам нужно уметь итерироваться по ключам, и делать это быстро. Как ты понимаешь, перебор всего массива buckets со всеми внутренними списками — это пиздец как долго. Исправить это можно хранением списка всех существующих ключей, и при вставке нового просто добавлять его в конец. Собственно, так мы и можем получить сохранение порядка вставки ключей без порчи асимптот. Такое решение, разумеется, весьма наивно, как там питонухи сделали — хуй знает.

                    > Кажется, что не всегда)
                    Честно говоря, «309 ns +- 10 ns» как-то не выглядит надёжно медленнее «320 ns +- 8 ns». А учитывая, что в замере скорости этот питушок брал медиану вместо минимума…
                    Ответить
                    • Во-первых тебе тоже придется брать хеш.

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

                      Но если мы не хотим коллизий хеша (потому что в обоих наших решениях можно схлопотать O(M), где M кол-во питухов с одинаковым хешем), то придется брать довольно большое N.

                      В моем решении поиск займет чуть больше времени, но не потребует массива размером N. А в твоем потребует.
                      Ответить
                      • Это не моё решение, это стандартная структура данных, которой скоро уже семьдесят лет стукнет.

                        Если «дерево» будет с достаточно большим N, то это ничем не будет отличаться от стандартной хэш-таблицы, кроме того, что тебе для поиска придётся разыменовывать хуеву тучу лишних уко-ко-козателей, что приведёт пирфоманс прямиком в жопу.

                        Хэш для таких штук берётся не питушарский, а царский, с максимально равномерным распределением. Поэтому в среднем в каждой корзине будет лежать по M/N (суммарное количество элементов/количество элементов в МАССИВЕ) элементов — эту метрику по-научному называют «load factor».

                        Если у тебя дерево будет N-ричным, то тебе тоже придётся делать N листьев, лол. По памяти так ты только проиграешь (не говоря уже про пирфоманс).
                        Ответить
                        • >то стандартная структура данных, которой скоро уже семьдесят лет стукнет.
                          Как и дереву.

                          >Если «дерево» будет с достаточно большим N, то это ничем не будет отличаться от стандартной хэш-таблицы
                          Именно

                          >кроме того, что тебе для поиска придётся разыменовывать хуеву тучу лишних уко-ко-козателей

                          Если у меня values будут сразу на первом уровне лежать в листьях, то не придется.

                          Если же дерево будет достаточно глубоким то да, придется.
                          Зато я буду подгружать с диска только нужные мне куски, а тебе придется выгружать в память весь массив и делать туда случайный доступ. Именно потому я и сказал про "не засрать всю память".


                          Впрочем, если твой hash целиком влезает в память то да, разумеется он лучше.
                          Ответить
                          • > Если у меня values будут сразу на первом уровне лежать в листьях, то не придется.
                            Остался один шаг: выкинуть ошмётки дерева и получить нормальный, человеческий хэшмассив.

                            > Зато я буду подгружать с диска только нужные мне куски, а тебе придется выгружать в память весь массив и делать туда случайный доступ.
                            Стоп-стоп-стоп, это как? У тебя первый уровень N-ричного дерева представляет из себя как раз массив из N элементов, как ты его собрался на куски дробить и почему это нельзя сделать с обычным массивом из N элементов?

                            > Если же дерево будет достаточно глубоким то да, придется
                            Джвух уровней будет достаточно, чтобы слить «классической» хэштаблице.

                            > Впрочем, если твой hash целиком влезает в память то да, разумеется он лучше.
                            Я очень сильно сомневаюсь, что при разработке словаря в «Питоне» учитывалась необходимость хранения данных, не влезающих в оперативную память.
                            Ответить
                            • >выкинуть ошмётки дерева и получить нормальный, человеческий хэшмассив.

                              Дерево можно углубить на след уровень, а массив -- нет.

                              >У тебя первый уровень N-ричного дерева представляет из себя как раз массив из N элементов,

                              Ты смешал два моих коммента, или я невнятно выразился.

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

                              А потом элементов становится сильно больше.
                              У дерева отрастает второй уровень. И вот тут уже мне нужно грузить только страницы с нужными мне данными, а тебе же придется иметь огромный массив.

                              Хотя наверное ты тоже можешь загрузить только кусок, потому что виртуальная память.

                              Значит ли это, что дерево сосет у hashtable для всех случаев, кроме тех, где данные должны упорядочиваться по значению?
                              Ответить
                              • > И вот тут уже мне нужно грузить только страницы с нужными мне данными
                                А как ты узнаешь, какие тебе нужны страницы? Ты же дерево строишь по хэшу, то есть очередной ключ окажется в абсолютно произвольном куске дерева. Если бы дерево было построено по самим ключам, тогда бы можно было делать предположения — например, что похожие ключи будут лежать где-то рядом.

                                > Значит ли это, что дерево сосет у hashtable для всех случаев, кроме тех, где данные должны упорядочиваться по значению?
                                В случаях, когда данных мало, а памяти много (гигабайт данных, десять гигабайт памяти, например) — да. Но когда данных становится очень много, и тратить гигабайты оперативы на пустые корзины становится затратно — тогда уже дерево вырывается вперёд. В этом случае, кстати, основным источников тормозов будут обращения к диску, так что промахи кэша практически перестанут влиять на скорость.
                                Ответить
                                • >А как ты узнаешь, какие тебе нужны страницы?
                                  Считаю их адреса из узлов дерева.

                                  Пусть первый уровень лежит в странице A.
                                  Второй -- в страницах B и С.
                                  Третий -- D, E, и F.

                                  Я читаю A, затем C и потом E.

                                  >и тратить гигабайты оперативы на пустые корзины становится затратно

                                  Я к этому и клонил, когда говорил про засирание памяти, но потом понял, что реально держать в памяти гигабайты пустого массива не нужно: ОС не будет ничего в память писать, пока ты туда в первый раз не обратишьтся.
                                  Ответить
                                  • > Я читаю A, затем C и потом E.
                                    Ну вот, а в случае с массивом достаточно вычислить хэш и загрузить в память в точности ту корзину, которую надо.
                                    Ответить
                                    • Да, я это уже понял.

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

                                      Главное, чтобы твоя корзина не пересекала границу страницы
                                      Ответить
                            • Кстати, а как ты сохранишь порядок добавления в hashtable?

                              В питоне, как я понял, они сделали отдельный массив с ключами
                              Ответить
                              • Я предложил держать список ключей и при вставке нового ключа добавлять его в конец за O(1). На поиск это влиять не будет никак, а вот с удалением придётся поебаться: наивно — держать в корзинах кортеж (ключ, значение, указатель_на_ключ_в_списке), не наивно — хз.
                                Как в «Питоне» реализовано — не знаю, не смотрел.
                                Ответить
                                • Можно джвусвязный, тогда удаление шустрое будет.
                                  Ответить
                                  • Тогда же в нем будут указатели, придется тратить время на их разыменование, не?
                                    Ответить
                                • То-есть тебе придется держать две структуры с одинаковыми данными: одну для сохранения ордера, другую для поиска, верно?

                                  > держать в корзинах кортеж (ключ, значение, указатель_на_ключ_в_списке),

                                  То-есть я за O(1) нашел нужный мне ключ, и дальше по нему нашел его место в массиве, и пошел на массиву читать следующие ключи?
                                  Ответить
                                  • В наивном вореанте — да.

                                    А можно, например, хранить список указателей на вставленные кортежи:
                                    Массив корзин
                                    |
                                    v
                                    0: (0x4: key, val), (0x5: key, val), ...
                                    1: (0x1: key, val), (0x6: key, val), ...
                                    .
                                    .
                                    .
                                    N: (0x3: key, val), (0x2: key, val), ...
                                    
                                    0x1..0x6 — адреса вставленных корзин, и пусть для примера они совпадают с
                                    порядковым номером вставки соответствующего ключа.
                                    Тогда вспомогательный список будет выглядеть как [0x1, 0x2, 0x3, 0x4, 0x5, 0x6].

                                    В этом случае, кстати, можно будет вспомогательный список преобразовать в дерево (ключ — порядковый номер вставки), тогда удоление элемента будет O(logN).
                                    Ответить
                                    • А теперь скажи честно: согласен-ли ты с тем, что требование о сохранении порядка вставки пиздецово всё усложняет?

                                      Ведь если бы не оно, то можно было бы использовать этот самый hashtable и течь
                                      Ответить
                                      • Нет, не согласен. В первую очередь это всё нужно для быстрой итерации по ключам, сохранение порядка вставки — просто полезный побочный эффект.
                                        Ответить
                                        • А что мешает итерироваться по ключам в твоей хештаблице? дырки?
                                          Ответить
                                          • Да. С учётом крайней распространённости в «Питоне» коньструкции «for key in some_dict: ...» её существенное ускорение за счёт незначительного увеличения расхода памяти выглядит разумным.

                                            А вообще, усложнение внутренней реализации для ускорения/улучшения стандартной библиотеки — это абсолютно нормально. Люди, которые делают делают реализацию языка, нужны именно для того, чтобы писать сложные вещи, которыми смогут пользоваться их менее продвинутые коллеги.
                                            Ответить
                                            • Ну если список ключей вводился ради ускорения итерации, то пусть будет. Если бы он вводился ради сохранения порядка вставки, то это был бы понос.

                                              Правда это ускорение всё равно пойдет по пизде, если я буду читать И ключ И значение.
                                              Но вероятно обычно значения получают не у всех ключей (иначе логичнее было бы хранить лист туплов)

                                              Кстати, в теории в бакете можно держать кол-во дырок до следующего непустого бакета (будет такой вот "связанный" список), но прыгать по нему будет крайне хуёво: придется или читать из памяти охулион пустых ячеек, или прыгать по страницам как блоха дроча диск.

                                              >тобы писать сложные вещи,
                                              Ради бога, но лишь бы это писалось ради серьезных задач.

                                              "Сохранение порядка вставки у дикта" такой задачей мне не кажется.
                                              А вот скорость итерации -- вполне.
                                              Ответить
                                              • > А вот скорость итерации -- вполне.
                                                Ну, собственно, сначала «CPython» перешёл на новую реализацию, которая сохраняет порядок ключей (то ли в 3.5, то ли в 3.6), и только потом это поведение зафиксировали официально.
                                                Статья про всю эту питушню: https://pbedn.github.io/post/ordered-dict-officially-ordered/.
                                                Python 3.5 brought us 4-100 times faster OrderedDict thanks to its implementation in C,
                                                before was written in Python. Python 3.6 improved a standard library dictionary,
                                                by making it use more compact representation. Now dictionary could use 20% to 25% less
                                                memory compared to Python 3.5, and the order of items was kept but as suggested it was
                                                only an implementation detail and should not be used officially (backwards compatibility).
                                                Well, in Python 3.7 it has been approved.
                                                Ответить
                                                • Подумалось:

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

                                                  Для тех же, кому нужно итерироваться по ключам -- сделать другую структуру (с массивом ключей рядышком).

                                                  Правда, это заставило бы программиста думать, и сильно усложнило бы язык.
                                                  Ответить
                                                  • На самом деле «честный hashtable» — это академическая хуйня для понимания базовых коньцептов. В реальном мире её допиливают напильниками до состояния неузнаваемости. Реальный пример: https://github.com/python/cpython/blob/master/Objects/dictobject.c — почти пять тыщщ строк сишного кода (насколько я понял, кстати, они там открытую адресацию используют и правильно делают: корзины — тормозная хуйня для ма-те-ма-ти-ков).

                                                    А по поводу отдельных структур на каждый чих хорошо сказано в вышеупомянутой статье:
                                                    Это первое и очевидное решение. Если мы не можем поменять std::unordered_map,
                                                    может нам просто добавить std::fast_map? Есть несколько причин, почему так делать
                                                    плохо. Добавление типов в стандартную библиотеку обходится дорого как с точки
                                                    зрения расходов на поддержку, так и с точки зрения образования. После введения
                                                    нового класса неизбежно появятся тысячи статей, в которых объясняется, какой
                                                    контейнер стоит использовать. К примеру, мне следует использовать std::scoped_lock
                                                    или std::lock_guard? А я понятия не имею! Мне нужно каждый раз гуглить.

                                                    (Кстати, я тоже без гугла не скажу, чем отличается std::scoped_lock от std::lock_guard и зачем они оба нужны, если есть std::unique_lock).

                                                    UPD: И да, «хэш(словарь, карта, ассоц. массив) в первую очередь используется для получения значения по ключу» не выглядит совсем уж очевидным утверждением.
                                                    Ответить
                                                    • Я за GO:

                                                      The Go language designers noticed that people were relying on the fact that keys were normally stored in the order they were added in, so they randomized the order in which the keys are iterated over. Thus, if you want to output keys in the order they were added in, you need to keep track of which value is in which position in the order yourself
                                                      Ответить
                                                      • Какой багор )))

                                                        UPD: Из пепа:
                                                        This observation is supported by the appearance of this proposal over
                                                        the years and the numerous times that people have been confused by the constructor
                                                        for OrderedDict. [3] [4] [5]

                                                        Какая разница подходов )))
                                                        Ответить
                                                        • > не выглядит совсем уж очевидным утверждением.
                                                          почему?

                                                          А для чего хеш?
                                                          Ответить
                                                          • > почему?
                                                            Потому что лично я часто вижу в питонокоде конструкцию «for key in some_dict: ...» и не могу бездоказательно согласиться с тем, что операция получения доступа по ключу настолько превалирует над итерацией, что последнюю можно игнорировать.
                                                            Ответить
                                                            • Так это потому что разрешили.

                                                              Если бы явно написали: "иди итерируйся в другое место, здесь dict не для этого", то все бы 10 раз подумали прежде чем.

                                                              А то небось питухи вместо листа пар используют дикт, и текут.

                                                              Кстати, в пандан: в коко есть "mutableSetOf<>() ". Так вот он создает не HashSet, а LinkedHashSet, то-есть тоже insertion order сохраняется.

                                                              Коко присоединился к остальным языкам, которые это делают
                                                              Ответить
                                                              • Я не знаю реальных примеров языков, в которых нельзя итерироваться по ассоциативным массивам. Как ты предлагаешь без итерации сериализовывать словарь, например?
                                                                Ответить
                                                                • Итерироваться можно, но это будет не очень быстрая операция.

                                                                  То-есть будет два дикта: оптимизированный для итерации и по памяти.
                                                                  Но я не то чтобы предлагаю, я скорее теоретизирую, потому что понимаю, что в 99% случаев это не важно
                                                                  Ответить
                                                                • Спокойной ночи! Пусть тебе приснится роща из красно-чёрных деревьев.
                                                                  Ответить
                                  • > То-есть я за O(1) нашел нужный мне ключ, и дальше по нему нашел его место в массиве, и пошел на массиву читать следующие ключи?
                                    Нет, поиск конкретного ключа во всех этих вореантах никак не изменяется. Вспомогательный список нужен для того, чтобы быстро итерироваться по всем ключам. А «указатель_на_ключ_в_списке» — чтобы можно было удалять элемент за O(1): ищешь его в таблице за O(1), удаляешь его из вспомогательного списка (тоже за O(1) благодаря тому, что у тебя сразу есть адрес нужного элемента вспомогательного списка), удаляешь из корзины ещё за один O(1).
                                    Ответить
                                    • Так а почему не использовать это для ренджей?

                                      Хочу все ключи от K8 и K99.

                                      Я могу найти K8 за O(1). Затем, я иду в список по смешению "указатель_на_ключ_в_списке", и дальше последовательно читаю ключи.
                                      Ответить
                                          • Лол, а почему у них для всех операций у словарей какая-то окололинейная питушня (или это логарифм? Не могу с ходу прикинуть)?
                                            Ответить
                                            • посмотри на шкалу секунд
                                              есть ощущение, что она не линейна

                                              хотя там и размер не линеен
                                              Ответить
                                              • Да, у них там и размер, и время нелинейны. Но в любом случае O(1) должно выглядеть как окологоризонтальная линия (как у «intersection_tiny» и «update_tiny», кстати).
                                                Может, у этих контейнеров поддерживаются какие-то хитрые свойства?
                                                Ответить
                        • errata:

                          строчку
                          "Если у меня values будут сразу на первом уровне лежать в листьях, то не придется."

                          следует читать как
                          "На каждом уровне мне придется делать бинарный поиск, например"
                          Ответить
                • Ну она явно не от сохранения порядка вставки быстрее стала. Скорее старая реализация была полным говном.
                  Ответить
                • > А дали такую гарантию после того, как в «CPython» изменили реализацию словаря на такую, которая гарантировала сохранение порядка вставки. И она оказалась быстрее, чем старая.

                  ахаха. такие анскилябры, что хуевый вариант оказался менее хуевым первого.
                  Ответить
                    • Памяти больше жрёт на поддержание гибридной структуры данных.
                      Ответить
                      • Разве? Для быстрой итерации по ключам нам в любом случае нужно держать дополнительный массив/список/etc этих ключей.
                        Ответить
                        • По пустым бакетам побегать не так уж дорого. По-моему в крестах так и делают. Разве нет?
                          Ответить
                          • В крестах обычно юзают «std::map» и текут, а у ней внутре дерево без таких проблем. А «std::unordered_map», ЕМНИП, стандартизаторы просрали, и из-за какого-то требования вроде доступа к корзинам весь пирфоманс и так оказался в жопе.
                            Ответить
                            • Есть какие-то опенсоурсе аналоги не анскильных unordered_map?
                              Ответить
                              • Охулиард. Недавно на ГК обсуждали https://habr.com/ru/post/490222/ (https://govnokod.ru/26455), там приводятся реальные примеры:
                                Множество разработчиков игр относятся крайне скептически к
                                стандартной библиотеке. Они скорее разработают свою альтернативу, к примеру EASTL,
                                чем воспользуются STL. У Facebook есть folly, у Google — abseil и так далее.

                                Какие разработчики игр «Facebook» и «Google» )))
                                Ответить
                        • >в любом случае нужно держать дополнительный массив/список/etc этих ключей.
                          Не совсем.
                          Там линкед лист бакетов, ключи в одном экземпляре, просто к ним прикручены next/prev.
                          Ответить
      • Перевёл на «PHP»:
        <?php
        
        $a = [1=>2, 2=>3];
        $b = [2=>3, 1=>2];
        var_export($a == $b);
        print PHP_EOL;
        var_export(json_encode($a) == json_encode($b));
        print PHP_EOL;

        Такая же питушня.
        Ответить
      • Перевел на D. Получил true true.
        int[string] a = ["1":2, "2":3];
        int[string] b = ["2":3, "1":2];
        writeln(a==b);
        writeln(JSONValue(a).toString()==JSONValue(b).toString());
        Ответить
        • use strict;
          use JSON;
          
          my %a = (2 => 3, 3 => 2);
          my %b = (3 => 2, 2 => 2);
          print((encode_json(\%a) eq encode_json(\%b)) ? 'eq' : 'nop');


          в перле сортирнулось по хешу ключа, и тоже не совпало
          Ответить
      • > a = {1:2, 2:3}
        > b = {2:3, 1:2}
        > print(a == b)

        Сранно. Но смотря на этот код я уже ожидаю подвоха. 99% что False.
        Ответить
      • Нормальное поведение.
        Кмк, сравнивать сложные типы через == в скриптухе западло.
        Должен быть какой-то хитрый map.equals_kv, map.equals_with_order или что-то в этом духе.
        Ответить
        • > Должен быть какой-то хитрый map.equals_kv, map.equals_with_order или что-то в этом духе.
          Змею можно заставить сравнивать словари с учётом порядка ключей через «OrderedDict()», кстати.
          >>> from collections import OrderedDict
          >>> {1:2, 3:4} == {3:4, 1:2}
          True
          >>> OrderedDict({1:2, 3:4}) == OrderedDict({3:4, 1:2})
          False
          Ответить
          • Это Питушатня.

            Как работает == никто точно не скажет, особенно когда типы разные (пусть даже это разные реализации мап).

            А когда ЯВНО указан метод для сравнения всё ясно и понятно.
            Ответить
  • Так выведи строки и посмотри
    Ответить

Добавить комментарий

Переведи на "PHP", guest!

    А не использовать ли нам bbcode?


    8