• LRU, метод вытеснения из кэша
    +1
    Спасибо, читал в процессе написания статьи, и решил не грузить. Добавил ссылку для интересующихся.
  • LRU, метод вытеснения из кэша
    +1
    Не только. Если лист в середине и спрашивается опять, то он должен быть поднят наверх.
    Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.
  • LRU, метод вытеснения из кэша
    0
    Ну да это и есть ответ на вопрос, просто исходный LRU описывается именно с временами. Да и мне кажется, что проще понять.
  • Олимпиада ФУПМ МФТИ по программированию для школьников
    0
    Уточнил у организаторов, просят вопросы задавать через проверяющую систему.
  • Олимпиада ФУПМ МФТИ по программированию для школьников
    +1
    Ну это выбирать участнику. Все языки не охватишь, главное, чтобы были наиболее популярные.
  • Олимпиада ФУПМ МФТИ по программированию для школьников
    0
    Это странно!
    Я не являюсь организатором и опубликовал эту новость по просьбе знакомого.

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

  • Дерево ван Эмде Боаса
    0
    Мне кажется это проблема присуща большинству структур данных.
    — двоичный поиск будет попадать мимо кеша поначалу
    — AVL и RB -деревья тоже могут попадать мимо кеша

    А большинство сортировок похоже будут хорошо ложится в кеш:)
  • Дерево ван Эмде Боаса
    0
    Поясню, а то два разных ответа. Я ответил про простой случай, в котором нет возможности FindNext и FindPrevios, а Invizory выше про дерево уже с такими возможностями.

    Такие соотношения вообще можно держать в хеше, и получится быстродействие O(N) (если грубо), что оптимальнее данного алгоритма, особенно на практике.
    Но чаще держат в B-деревьях, так как они оптимизированы под работу блочной структурой диска со сложность N log N.
  • Дерево ван Эмде Боаса
    0
    Вместо булева T.exists[] будет структура с доп. информацией.
    А те же проверки заменятся на равно (не равно) null.
  • Дерево ван Эмде Боаса
    0
    А что с памятью? Вроде в статье есть беглая оценка в O(U) — это странно.
    Ведь если каждая операция log(log(U)) времени, то памяти займем не более чем n * log(log(U)), если не делать зверских предобработок.
  • Теория Игр и функция Шпрага-Гранди
    0
    1. Написать, что after[k] берется равным bf * before[k].
    2. Фраза где K — количество камней… явно имеется в виду где K — номер кучки и т.д.
    3. Показать, что, что after[k] < before[k], за счет выбора k.
  • Теория Игр и функция Шпрага-Гранди
    0
    Тогда еще одно непонятное предложение:

    Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
    af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (af ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.

    Вообще переход не простой. ИМХО можно написать подробнее, а тут еще и ошибка, так что врубиться в него могут только настойчивые.

    Как минимум надо переписать так:
    Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
    af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (bf ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
  • Теория Игр и функция Шпрага-Гранди
    +1
    Тоже странное предложение:

    Если bf == 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af == bf[i] ^ af[i], но так как before[i] != after[i], а bf != 0, то переход ведет в выигрышное состояние.

    1. Вначале предполагается, что bf == 0, а затем используется, что bf != 0.
    2. В одном предложении используются то before[i], то bf[i]. Разные ли это вещи?
    Предлагаю переписать, на что-то вроде:

    Если bf = 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af = bf[i] ^ af[i], но так как bf[i] != af[i], то af != 0, а значит переход ведет в выигрышное состояние по индукции.
  • Теория Игр и функция Шпрага-Гранди
    0
    В наших школах и университетах почти всегда преподают, что 0 не натуральное.
    А статья на русском, значит логично заменить на неотрицательные.
  • Теория Игр и функция Шпрага-Гранди
    0
    Натуральные и положительные числа в сумме не дают 0, если их самих не ноль. Это, хотел сказать GORKOFF. Если конечно там не имеется в виду xor-сумма, но вроде там еще рано.
    Мне кажется эту фразу просто можно выкинуть.
  • Олимпиадное хобби. Разминка
    0
    Да, я понял, что неправ) Думал, что стандартные перестановки работают только с перестановками без повторяющихся элементов. Эта задача старая. В те времена были задачи, которые сейчас можно решить стандартными средствами (их немного).

    Я хотел сказать, что стандарты знать надо, но большинство задач имеют алгоритм решения по месту.
    Например, могли попросить генерировать правильные скобочные последовательности, какие-нибудь обходы или еще чего. Тут стандартом не обойдешься, придется думать алгоритм по месту. Но в целом ваше замечание правильное.
  • Олимпиадное хобби. Разминка
    –1
    А, да. Я думал, что перестановки работают только с чистыми перестановками (я давно на плюсах не пишу).
  • Олимпиадное хобби. Разминка
    –1
    Предложите решение с помощью std:next_permutation, мне кажется что это будет задачка покруче исходной)
  • Распределенная файловая система GFS (Google File System)
    0
    Под Hadoop я имел в виду HDFS
  • Распределенная файловая система GFS (Google File System)
    –1
    Да, но есть альтернатива — Hadoop, который, как я понимаю изначально строился по подобию GFS.
  • Распределенная файловая система GFS (Google File System)
    +1
    Про MapReduce и Bigtable — в точку. Постараюсь найти свободное время.
  • Распределенная файловая система GFS (Google File System)
    +4
    Попробуйте прочитать исходную статью, возможно их английский лучше, чем мой русский.
    Также можно почитать аналогичные статьи про hadoop, например www.insight-it.ru/net/scalability/hadoop/
  • Распределенная файловая система GFS (Google File System)
    0
    Что имеется в виду? Бенчмарки в той же статье, или же какая-то другая статья?

    Вообще хотелось бы развить тему, как руки дойдут