1. 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, 30 Июня 2020

    Комментарии (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.
                                            Ответить
                                      • Ответить
                                        • показать все, что скрытоvanished
                                          Ответить
                                          • Да даже в десятичном можно походу. В десятке есть 2, поэтому двоичную дробь таки можно записать как десятичную. Проблемы начинаются только в обратную сторону, когда какое-нибудь 0.1 пытаешься записать как двоичную дробь.
                                            Ответить
                                        • То есть возможны варианты, что я заассайню во флоат compile-time литерал, а потом выведу его на экран и получу неожиданность?
                                          Ответить
                                          • показать все, что скрытоvanished
                                            Ответить
                                          • Ну да. Он испортится в момент его преобразования из твоего текста в дабл. Выведется то он уже без потерь, но может не совпасть с тем, что ты писал.

                                            Типа пишешь 0.1 а получаешь 0.99999999 или 0.100000001. Потому что между ними более подходящих чисел во флоате нет.
                                            Ответить
                                            • Я надеюсь, что там всё же подразумевалось 0.09999999, а то мне совсем страшно стало!
                                              Ответить
                                              • Да, 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блабла, да. А вот там какую-нибудь постоянную Планка уже фиг, а потому какая мне разница, какая там дробь?
                                        Ответить
                            • В виде десятичной дроби её ма-те-ма-ти-чес-ки невозможно вывести. Придётся прям двоичное представление вываливать хексами, а это нечитаемо.
                              Ответить
                              • Я именно это и имел ввиду: двоичное представление.
                                Хочешь кексом, хочешь базой64, хочешь чем хочешь.

                                Про читаемость https://govnokod.ru/26782#comment556851
                                Ответить
      • Минимальный пример, который на 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? Я же их по имени юзаю.
                    Ответить
                    • показать все, что скрытоvanished
                      Ответить
                      • Да просто у других скриптушков порядок сохранялся, вот питонятам и завидно стало. Никакой особой логики или пользы в этом нет.
                        Ответить
                        • показать все, что скрытоvanished
                          Ответить
                          • В жс вроде как раз перед питоном такую гарантию дали?

                            В пхп вроде тоже есть.
                            Ответить
                            • показать все, что скрытоvanished
                              Ответить
                              • Что такое symbol?
                                Ответить
                                • Это такой специальный уникальный объект, который никогда не равен никакому другому. «Никогда», правда, в стиле «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');
                                    
                                    Это же та самая херня, которую скучные дяди с галстуками в своих коболах решали с
                                    середины прошлого века: глобальные имена, глобальные имена с ручными
                                    префиксами, пространства имён, локальные имена, замыкания… Джаваскриптовые
                                    хипстеры как всегда решительно встали в самое начало пути изобретения колеса.
                                    Ответить
                                • показать все, что скрытоvanished
                                  Ответить
                            • показать все, что скрытоvanished
                              Ответить
                          • у пхп, конечно же
                            Ответить
                    • 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.
                      Ответить
                      • показать все, что скрытоvanished
                        Ответить
                        • > то-есть если я сортирну их явно перед выводом, то все будет тормозить?
                          Так смысл не в том, чтобы их отсортировать, смысл в том, чтобы показать их в том порядке, в каком они были переданы в функцию.

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

                          Мне, в общем-то, наиболее полезным показался последний пример, с «Specifying argument priority by order».
                          Ответить
                          • показать все, что скрытоvanished
                            Ответить
                            • > Почему не сделать это при объвлении?
                              «kwargs» — это просто название аргумента, оно может быть любым. То, что в этот аргумент складываются именованные параметры, определяют две звёздочки перед нем. В пепе, в разделе альтернатив, есть предложение расширить синтаксис тремя звёздочками, но это, очевидно, хуёвая идея. «New syntax is only added to Python under the most dire circumstances».
                              Ответить
                              • показать все, что скрытоvanished
                                Ответить
                                • > прошу питона сохранить порядок
                                  Для этого разработчикам «Питона» придётся расширить синтаксис, а это — плохая идея. К расширению синтаксиса следует прибегать только в самых печальных обстоятельствах, когда без этого будет совсем уж говно.
                                  Ответить
          • показать все, что скрытоvanished
            Ответить
            • > зачем? зачм?
              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».
                Ответить
              • показать все, что скрытоvanished
                Ответить
                • Я даже больше скажу: ключи dict'а ты в любом случае не можешь в дерево сложить. dict — это хэш-массив, его ключи не обязаны быть сравнимыми иметь порядок. Собственно, дерево — это питушня: зачем нужны питушарские O(logN) на поиск, когда можно сделать амортизированное царское O(1)?

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

                  > Ты может и для сета хочешь сохранять порядок?
                  А такой сет вполне можно эмулировать имеющимся словарём, причём с сохранением всех асимптот.
                  Ответить
                  • показать все, что скрытоvanished
                    Ответить
                    • > Далее, ты пихаешь их в дерево по хешу
                      А зачем? Ты получишь поиск за питушарские 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». А учитывая, что в замере скорости этот питушок брал медиану вместо минимума…
                      Ответить
                      • показать все, что скрытоvanished
                        Ответить
                        • Это не моё решение, это стандартная структура данных, которой скоро уже семьдесят лет стукнет.

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

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

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

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

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

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

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

                                      А можно, например, хранить список указателей на вставленные кортежи:
                                      Массив корзин
                                      |
                                      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).
                                      Ответить
                                      • показать все, что скрытоvanished
                                        Ответить
                                        • Нет, не согласен. В первую очередь это всё нужно для быстрой итерации по ключам, сохранение порядка вставки — просто полезный побочный эффект.
                                          Ответить
                                          • показать все, что скрытоvanished
                                            Ответить
                                            • Да. С учётом крайней распространённости в «Питоне» коньструкции «for key in some_dict: ...» её существенное ускорение за счёт незначительного увеличения расхода памяти выглядит разумным.

                                              А вообще, усложнение внутренней реализации для ускорения/улучшения стандартной библиотеки — это абсолютно нормально. Люди, которые делают делают реализацию языка, нужны именно для того, чтобы писать сложные вещи, которыми смогут пользоваться их менее продвинутые коллеги.
                                              Ответить
                                              • показать все, что скрытоvanished
                                                Ответить
                                                • > А вот скорость итерации -- вполне.
                                                  Ну, собственно, сначала «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.
                                                  Ответить
                                                  • показать все, что скрытоvanished
                                                    Ответить
                                                    • На самом деле «честный 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: И да, «хэш(словарь, карта, ассоц. массив) в первую очередь используется для получения значения по ключу» не выглядит совсем уж очевидным утверждением.
                                                      Ответить
                                    • > То-есть я за O(1) нашел нужный мне ключ, и дальше по нему нашел его место в массиве, и пошел на массиву читать следующие ключи?
                                      Нет, поиск конкретного ключа во всех этих вореантах никак не изменяется. Вспомогательный список нужен для того, чтобы быстро итерироваться по всем ключам. А «указатель_на_ключ_в_списке» — чтобы можно было удалять элемент за O(1): ищешь его в таблице за O(1), удаляешь его из вспомогательного списка (тоже за O(1) благодаря тому, что у тебя сразу есть адрес нужного элемента вспомогательного списка), удаляешь из корзины ещё за один O(1).
                                      Ответить
                          • показать все, что скрытоvanished
                            Ответить
                  • Ну она явно не от сохранения порядка вставки быстрее стала. Скорее старая реализация была полным говном.
                    Ответить
                  • > А дали такую гарантию после того, как в «CPython» изменили реализацию словаря на такую, которая гарантировала сохранение порядка вставки. И она оказалась быстрее, чем старая.

                    ахаха. такие анскилябры, что хуевый вариант оказался менее хуевым первого.
                    Ответить
                    • Чем новый вореант плох?
                      Ответить
                      • Памяти больше жрёт на поддержание гибридной структуры данных.
                        Ответить
                        • Разве? Для быстрой итерации по ключам нам в любом случае нужно держать дополнительный массив/список/etc этих ключей.
                          Ответить
                          • По пустым бакетам побегать не так уж дорого. По-моему в крестах так и делают. Разве нет?
                            Ответить
                            • В крестах обычно юзают «std::map» и текут, а у ней внутре дерево без таких проблем. А «std::unordered_map», ЕМНИП, стандартизаторы просрали, и из-за какого-то требования вроде доступа к корзинам весь пирфоманс и так оказался в жопе.
                              Ответить
                              • показать все, что скрытоvanished
                                Ответить
                                • Охулиард. Недавно на ГК обсуждали 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());
          Ответить
        • > 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
            Ответить
            • Это Питушатня.

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

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

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