Компания Hola регулярно проводит конкурсы для программистов, которые, как правило, являются интересными и довольно сложными. В своем весеннем конкурсе Hola предлагала решить такую задачу (оригинал задачи):
В Node.js входит реализация высокопроизводительного связного списка: http://github.com/joyent/node/blob/master/lib/_linklist.js
Эта реализация написана специально для хранения idle timeouts, и не позволяет одному объекту участвовать в нескольких списках.
Задача конкурса заключается в написании своей реализации связанного списка, в котором не будет ограничений, указанных выше. При этом производительность не должна ухудшиться. Также к решению нужно приложить оценку производительности.
Анализ
На первый взгляд задача кажется довольно сложной, ведь ускорить вот такой код, кажется нереальным:
1 2 3 4 5 6 7 8 | // remove a item from its list and place at the end. function append(list, item) { remove(item); item._idleNext = list._idleNext; list._idleNext._idlePrev = item; item._idlePrev = list; list._idleNext = item; } |
К тому же, наш код должен быть более гибким — каждый из этих объектов (list и item) должен иметь возможность участвовать в нескольких списках, а это значит, что наш код будет выглядеть примерно так:
1 2 3 4 5 6 7 | function append(list, item, list_key) { remove(item, list_key); // remove item from list with key 'list_key' item._idleNext[list_key] = list._idleNext[list_key]; list._idleNext[list_key]._idlePrev[list_key] = item; item._idlePrev[list_key] = list; list._idleNext[list_key] = item; } |
Такой код в общем случае не будет быстрее чем оригинальный, так что нам нужно придумать более гибкое и быстрое решение. Судя по всему, решение задачи сводится к тому, чтобы придумать как к одному объекту привязать несколько пар параметров _idleNext и _idlePrev. При этом каждая пара должна обозначать принадлежность к своему связанному списку.
Вариантов решения несколько:
— Использовать массив item._idleNext[list_key] или item[list_key]._idleNext
— Использовать генерацию строки параметра item['_idleNext'+list_key]
— Использовать случайное имя параметра (item[random_key]), хранить отдельным списком только эти случайные имена итд.
Каждый из этих вариантов имеет узкие места, где теряется производительность.
Решение
1) Для начала оформим нашу реализацию связанного списка в виде класса. Это напрашивается, т.к. для поддержки нескольких связанных списков будет удобнее обращаться к ним как к экземплярам класса. Под «классами» имеются в виду не настоящие классы EcmaScript 6, а «классы» сгенерированные из CoffeeScript.
Получим что-то подобное (код на CoffeeScript):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class List102 constructor: ()->... init: (list)-> list.next_key = list list.prev_key = list # show the most idle item peek: (list)->... # remove the most idle item from the list shift: (list)->... # remove a item from its list remove: (item)->... # remove a item from its list and place at the end. append: (list, item)->... isEmpty: (list)->... module.exports = List102 |
Реализация всех функций не отличается от оригинальных, кроме смены названий параметров на next_key и prev_key. Таким образом становится действительно удобно работать со связанными списками:
1 2 3 4 5 6 | var List102 = require('./List102/List102'); var list1 = new List102(); // first list var list2 = new List102(); // second list var object = /*some object*/; list1.init(object); list2.init(object); // Yes, object holds another list pointers! |
Однако в этом коде не решена проблема именования параметра next_key и prev_key, ведь в строках 5 и 6 этот параметр будет перезаписан и списки не будут работать корректно.
2) На самом деле решение очень простое — нужно в конструкторе класса изменять исходный код всего экземпляра класса. При этом в пределах экземпляра изменить названия next_key и prev_key на что-то более уникальное. Это можно сделать если каждую функцию в классе привести к строке (@[func_name]+»), изменить полученный исходный код и объявить заново функцию (eval('this.'+func_name+'='+new_code)).
Исходный код конструктора класса List102:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | constructor: ()->; key = @generateKey() next_key = 'n'+key prev_key = 'p'+key # replacing code of functions in runtime =) for _func of @ if typeof @[_func] == 'function' and _func != 'generateKey' source = @[_func]+"" new_code = source .replace(/next_key/g, next_key) .replace(/prev_key/g, prev_key) if new_code!=source eval('this.'+_func+'='+new_code) |
Таким образом при создании экземпляра класса в runtime мы заменили все next_key и prev_key в классе на какую-то случайную строку. В этом случае полученное случайное имя параметра больше не нуждается в дополнительной обработке (конкатенации, дополнительных массивах итд). Таким образом при дальнейшем обращении к экземпляру класса наш связанный список будет обращаться непосредственно к нужному параметру. Тем самым мы добиваемся производительности не хуже, чем в оригинальном варианте.
Полную версию решения можно найти в моем репозитории на github: https://github.com/mubinov/hola2015solution
Оценка производительности
В benchmark.js находится тест для оценки производительности оригинального связанного списка и моего решения. Результат оценки:
Benchmark for original linklist:
Timer 1 (creating and appending 100k items): 972ms
Timer 2 (shift random 10k items): 1540ms
Timer 3 (peek random 10k items): 276ms
Timer 4 (remove random 10k items): 413ms
Benchmark for List102:
Timer 1 (creating and appending 100k items): *823ms*
Timer 2 (shift random 10k items): *1456ms*
Timer 3 (peek random 10k items): *261ms*
Timer 4 (remove random 10k items): *392ms*
Full table
original linklist List102
Timer 1 972 823
Timer 2 1540 1456
Timer 3 276 261
Timer 4 413 392
Стоит пояснить, что тест синтетический и показывает только то, насколько быстро проходят тест оба решения. В тесте на моей конфигурации сервера с небольшим перевесом побеждает List102 (мое решение), что говорит о том, что в общем случае показатели производительности не ухудшились.
Ссылки:
Задание конкурса
Финальные работы и итоги
Мое решение