Комментарии 22
Статья не плохая, но уж слишком сильно вы на денежный вопрос упирали. По моему тех, кто ставит минусы, именно этот момент раздражает.
> Здесь, очевидно, имеется в виду непосредственное участие одного и того же узла в двух и более списках
Очевидно?
Оригинал «and does not allow list parent to hold two or more different lists in the parent list object».
Что такое «list parent» я вообще не имею понятия, «list head» или «list previous node» еще можно понять. Возможно сам объект списка?
Может быть действительно дело в том, что узлы могут принадлежать только одному списку, но мне это не совсем ясно даже из оригинала. Типа list parent — объект, к которому «примешана» возможность работы в списках.
Видимо самостоятельно анализировать требования у меня не выходит :)
Очевидно?
Оригинал «and does not allow list parent to hold two or more different lists in the parent list object».
Что такое «list parent» я вообще не имею понятия, «list head» или «list previous node» еще можно понять. Возможно сам объект списка?
Может быть действительно дело в том, что узлы могут принадлежать только одному списку, но мне это не совсем ясно даже из оригинала. Типа list parent — объект, к которому «примешана» возможность работы в списках.
Видимо самостоятельно анализировать требования у меня не выходит :)
Типа list parent — объект, к которому «примешана» возможность работы в списках.
По-моему так, да. Вообще фигня какая-то написана, мне не нравится вся эта идея целиком — примеси делать. Непременно же потом захочется сериализовать эту штуку и отдать юзеру / сложить в базу данных, придется эти поля фильтровать.
Задача откровенно дурацкая, к слову. Одновременно простая и невозможная.
Если нужно именно сохранить сложность O(1) и O(n) для добавления/удаления и поиска соответственно, и допустимы незначительные замедления (доли или единицы процентов от общего времени выполнения) из-за добавления дополнительного функционала — решение элементарное.
Банально заменяется обращение к _idleNext и _idlePrev на что-то вроде для, например, функции peek
То есть решение довольно очевидное и «в лоб». Функция сложности не меняется, но возрастают затраты на дополнительные обращения.
А вот дальше начинается абсолютная дурость. Из-за неизвестной среды исполнения становится непонятно, что можно и что нельзя использовать, потому что подобный код замечательно оптимизируется через WeakMap, который может очень хорошо дать прироста в нативном исполнении.
А больше его и не оптимизировать толком никак, потому что проще и эффективнее, чем это сделано сейчас, сделать не выйдет. В основном потому что код практически эквивалентен определению двусвязного списка самого по себе и не обладает дополнительным обвесом из кода, оптимизировать его возможно будет только под какие-то специфические платформы. Либо сделать извращенную реализацию двусвязного списка поверх — опять же — какого-нибудь WeakSet, но тут вновь вопрос о том, какие требования по платформам.
Если нужно именно сохранить сложность O(1) и O(n) для добавления/удаления и поиска соответственно, и допустимы незначительные замедления (доли или единицы процентов от общего времени выполнения) из-за добавления дополнительного функционала — решение элементарное.
Банально заменяется обращение к _idleNext и _idlePrev на что-то вроде для, например, функции peek
function peek(list) {
if (list.__prevPointers[listKey] == list) return null;
return list.__prevPointers[listKey];
}
То есть решение довольно очевидное и «в лоб». Функция сложности не меняется, но возрастают затраты на дополнительные обращения.
А вот дальше начинается абсолютная дурость. Из-за неизвестной среды исполнения становится непонятно, что можно и что нельзя использовать, потому что подобный код замечательно оптимизируется через WeakMap, который может очень хорошо дать прироста в нативном исполнении.
А больше его и не оптимизировать толком никак, потому что проще и эффективнее, чем это сделано сейчас, сделать не выйдет. В основном потому что код практически эквивалентен определению двусвязного списка самого по себе и не обладает дополнительным обвесом из кода, оптимизировать его возможно будет только под какие-то специфические платформы. Либо сделать извращенную реализацию двусвязного списка поверх — опять же — какого-нибудь WeakSet, но тут вновь вопрос о том, какие требования по платформам.
Согласен.
Среда исполнения: можно предположить, что Node.js.
Среда исполнения: можно предположить, что Node.js.
Те же мысли.
Может ожидается какое-то красивое ООП? Ну вроде как ручками listKey пробрасывать неудобно, можно «класс»-обертку соорудить, которая бы еще и автоматом бы примешивала эти внутренние свойства (prev / next). Можно, к примеру, еще и допилить чтобы имена этих internal-полей были не жёстко захаркожены, а подстраивались, в случае если у исходного объекта они уже есть (банально перебираем __prev_X, скажем, а чтобы опознать, что это наше internal-поле, можно и наше magic-значение записать).
Если «Во-первых, внимательный читатель уже догадался, что организаторы хотят увидеть прежде всего бенчмарк» действительно так, то это немножко меняет дело, но не сильно.
Тем более, по бенчмарку тоже есть вопросы.
В общем, набросаю на выходных как для меня всё это выглядит, посмотрим.
Может ожидается какое-то красивое ООП? Ну вроде как ручками listKey пробрасывать неудобно, можно «класс»-обертку соорудить, которая бы еще и автоматом бы примешивала эти внутренние свойства (prev / next). Можно, к примеру, еще и допилить чтобы имена этих internal-полей были не жёстко захаркожены, а подстраивались, в случае если у исходного объекта они уже есть (банально перебираем __prev_X, скажем, а чтобы опознать, что это наше internal-поле, можно и наше magic-значение записать).
Если «Во-первых, внимательный читатель уже догадался, что организаторы хотят увидеть прежде всего бенчмарк» действительно так, то это немножко меняет дело, но не сильно.
Тем более, по бенчмарку тоже есть вопросы.
В общем, набросаю на выходных как для меня всё это выглядит, посмотрим.
Ну формальное требование — «не медленнее», значит, бенчмарк должен банально замерять то, что каждая из операций выполняется не медленнее: creating, updating, traversal. Это можно достигнуть только через вот да, эти «волшебные» ключи, потому что даже выборка по двум ключам не так эффективна.
Теоретически — да, это, пожалуй, единственный вариант, но апи будет такииим гемморойным… К тому же — придется кэшировать строки, потому что операция создания строки '__prev_' + x тоже ресурс жрет. Соответственно — нужна автоматическая генерация строк с их кэшированием.
В итоге код будет вида list[prevKey[x]], что в итоге тоже равно является выборкой по ключам. В итоге — тоже не катит.
Примесью в виде красивого ООП — я уже сказал, это чистый WeakMap, есть замечательный полифилл от Брэндона Бенви, который сумел создать скрытые свойства элементов и на этом сделал поддержку множественных WeakMap на одном объекте, у которых не течет память. Код практически эквивалентен, я как раз начал ковыряться с того, что взял его полифилл и выкинул все лишнее. Получилось именно так, как я сказал выше — двойная выборка по ключам, и минимальная просадка по перформансу. И вот что с этим дальше делать — вообще без понятия.
Теоретически — да, это, пожалуй, единственный вариант, но апи будет такииим гемморойным… К тому же — придется кэшировать строки, потому что операция создания строки '__prev_' + x тоже ресурс жрет. Соответственно — нужна автоматическая генерация строк с их кэшированием.
В итоге код будет вида list[prevKey[x]], что в итоге тоже равно является выборкой по ключам. В итоге — тоже не катит.
Примесью в виде красивого ООП — я уже сказал, это чистый WeakMap, есть замечательный полифилл от Брэндона Бенви, который сумел создать скрытые свойства элементов и на этом сделал поддержку множественных WeakMap на одном объекте, у которых не течет память. Код практически эквивалентен, я как раз начал ковыряться с того, что взял его полифилл и выкинул все лишнее. Получилось именно так, как я сказал выше — двойная выборка по ключам, и минимальная просадка по перформансу. И вот что с этим дальше делать — вообще без понятия.
Кто хочет решать — читайте внимательно оригинал =)
Учавствовал в предидущем конкурсе по С от Хола. Всем решившим была обещана награда. Отправил решение — ни ответа ни привета. Написал им первый спустя 2 недели. Сказали что какая-то девочка проверяет. Уже примерно год как их девочка проверяет. Всем участникам удачи!
Да, с гарантиями жопа: как получить деньги и как понять, что твоё решение не лучшее? (приведёны ли будут варианты решений)
Может поэтому на втором конкурсе было так мало толкового народу?
Может поэтому на втором конкурсе было так мало толкового народу?
Оно было плохо организовано, да. «Плохие» решения периодически оставались без ответа.
Могли бы оповестить о том что проверили, но решение не устраивает.
Да. На эту тему я с ними ругался, т.к. мне периодически рассказывали про такие случаи.
Хоть это и не извиняет организаторов, объясняется всё следующим образом: этой инициативой никто не занимался на самом деле. Хола — совсем маленький стартап, там каждый сотрудник «работает на нескольких работах», сиречь делает много разноплановых вещей. (Salespeople я за сотрудников, конечно, не считаю — они как аквариумные рыбки.)
Поэтому некоторые аспекты долгое время страдали. Например, оформление сайта и продуктов компании создавалось программистами по остаточному принципу. (Сейчас это уже не так.)
А больше всего от отсутствия фокуса страдают коммуникации с людьми, будь то пользователи, соискатели, кто угодно за пределами фирмы. Это, конечно, плохо.
Хоть это и не извиняет организаторов, объясняется всё следующим образом: этой инициативой никто не занимался на самом деле. Хола — совсем маленький стартап, там каждый сотрудник «работает на нескольких работах», сиречь делает много разноплановых вещей. (Salespeople я за сотрудников, конечно, не считаю — они как аквариумные рыбки.)
Поэтому некоторые аспекты долгое время страдали. Например, оформление сайта и продуктов компании создавалось программистами по остаточному принципу. (Сейчас это уже не так.)
А больше всего от отсутствия фокуса страдают коммуникации с людьми, будь то пользователи, соискатели, кто угодно за пределами фирмы. Это, конечно, плохо.
Так как:
* На первый конкурс «хороший» ответ не был опубликован даже после окончания конкурса.
<субъективно>
* Денег работникам предлагают мало.
* Работники увольняются из-за плохой обстановки.
</субъективно>
Мотивация участия в конкурсе понижена.
* На первый конкурс «хороший» ответ не был опубликован даже после окончания конкурса.
<субъективно>
* Денег работникам предлагают мало.
* Работники увольняются из-за плохой обстановки.
</субъективно>
Мотивация участия в конкурсе понижена.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Внутри поста деньги. Очередной JavaScript-конкурс