A🌚
Size: a a a
2020 December 11
in
Про интересные вопросы на собесе - у меня когда-то попросили реализовать ordered dict, мне понравился вопрос)
и что ты ответил? :)
A🌚
и что ты ответил? :)
Код писал, там есть неочевидности со сложностью поиска и вставки, поэтому наверное и запомнилось
RB
и что, ты прям ordered dict реализовывал или просто завел список чтобы порядок ключей хранить?
A🌚
и что, ты прям ordered dict реализовывал или просто завел список чтобы порядок ключей хранить?
Ну до реализации самой хэш таблицы я тогда не дошёл) в итоге ограничился обычным dict и двусвязным списком для хранения порядка
SA
А зачем там двусвязный список? Можно же односвязным обойтись.
SA
А, чтобы reversed работал?
БС
а чем не устраивает питоновский list и dict ?
A🌚
А, чтобы reversed работал?
Ага
A🌚
а чем не устраивает питоновский list и dict ?
Сложность удаления элемента O(n), а хотелось константное время
RB
А как связный список поможет? в нем поиск элемента O(n)
БС
ну зачем удалять? можно просто помечать удаленным. Потом вакуум запускать.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
A🌚
А как связный список поможет? в нем поиск элемента O(n)
А для этого есть dict
RB
ну зачем удалять? можно просто помечать удаленным. Потом вакуум запускать.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
лови постгреса!
A🌚
ну зачем удалять? можно просто помечать удаленным. Потом вакуум запускать.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
Ну такого мне в голову не приходило)
A🌚
ну зачем удалять? можно просто помечать удаленным. Потом вакуум запускать.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
Ну и эта, дополнительная косвенная адресация как в классическом связанном списке, даёт такой охренительное пенальти, что O(n) это не страшно получается.
А какой именно пенальти даёт дополнительная косвенная адресация? По памяти? Или на сборщик мусора?
БС
пенальти даёт косвенная адресация, так как память в компьютерах очень медленная (по сравнению с гигагерцами процессора), поэтому делают всякие кеши, предчтения и прочее..
Сейчас ищу статью, но по памяти получаются такие порядки:
чтение значения из кеш линии -- пара тактов
чтение значения из кеша L2 -- десятки тактов
чтение значения из L3 -- под сотню
Чтение из основной памяти -- несколько сотен тактов.
Когда значения лежат рядом, они при первом обращении попадут во все уровни кешей и будут лежать рядом и пенальти не будет.
А с двусвязным списком у тебя получается чтение из рандомной памяти, которая 100% не будет в L1, но вероятно будет в L2/L3...
Сейчас ищу статью, но по памяти получаются такие порядки:
чтение значения из кеш линии -- пара тактов
чтение значения из кеша L2 -- десятки тактов
чтение значения из L3 -- под сотню
Чтение из основной памяти -- несколько сотен тактов.
Когда значения лежат рядом, они при первом обращении попадут во все уровни кешей и будут лежать рядом и пенальти не будет.
А с двусвязным списком у тебя получается чтение из рандомной памяти, которая 100% не будет в L1, но вероятно будет в L2/L3...
БС
Пока нашел вот эту статью: http://alenacpp.blogspot.com/2010/04/blog-post.html
но там ссылки на другие, которые я сейчас не смотрел. Я помню что про кеши и списки хорошо было написано у некого калинина. Но либо блог умер, либо я что то не так помню, не могу найти :-(
А еще бывает такие парадоксы, чтобы программа быстрее работала, но больше памяти использовать
но там ссылки на другие, которые я сейчас не смотрел. Я помню что про кеши и списки хорошо было написано у некого калинина. Но либо блог умер, либо я что то не так помню, не могу найти :-(
А еще бывает такие парадоксы, чтобы программа быстрее работала, но больше памяти использовать
A🌚
пенальти даёт косвенная адресация, так как память в компьютерах очень медленная (по сравнению с гигагерцами процессора), поэтому делают всякие кеши, предчтения и прочее..
Сейчас ищу статью, но по памяти получаются такие порядки:
чтение значения из кеш линии -- пара тактов
чтение значения из кеша L2 -- десятки тактов
чтение значения из L3 -- под сотню
Чтение из основной памяти -- несколько сотен тактов.
Когда значения лежат рядом, они при первом обращении попадут во все уровни кешей и будут лежать рядом и пенальти не будет.
А с двусвязным списком у тебя получается чтение из рандомной памяти, которая 100% не будет в L1, но вероятно будет в L2/L3...
Сейчас ищу статью, но по памяти получаются такие порядки:
чтение значения из кеш линии -- пара тактов
чтение значения из кеша L2 -- десятки тактов
чтение значения из L3 -- под сотню
Чтение из основной памяти -- несколько сотен тактов.
Когда значения лежат рядом, они при первом обращении попадут во все уровни кешей и будут лежать рядом и пенальти не будет.
А с двусвязным списком у тебя получается чтение из рандомной памяти, которая 100% не будет в L1, но вероятно будет в L2/L3...
Как ты далеко залез. Тут проседание будет только при итерации вроде как
БС
объясняется это тем, что оптимально делать структуры в размер кэш линии (16 байт (или dwordов) 10 лет назад было, как сейчас -- хз), чтобы было как можно меньше вытеснений из кеша и конкуренции..