Элементарные структуры данных (23 октября 2013)

  1. MergeSort, дополнение
    1. Он умеет считать общее количество инверсий
    2. А еще он умеет считать количество для каждого элемента [код]
  2. Какие есть структуры
    1. Бор (на примере задачи про IP адреса). Памяти = 256*k, время ответа на запрос = 4. [код] [картинка]
    2. Дерево по неявному ключу (реклама, подумать про стандартные структуры данных) [код]
  3. Учимся пользовать set-ом и profiler-ом
    1. Задача: отсортировать массив операцией reverse отрезка
    2. Решение: bfs с запоминанием [код]
    3. Тестируем решение: пишем генератор [код]
    4. Тестируем решение: что такое RuntimeError? Чаще всего выход за пределы допустимой памяти.
    5. Оптимизируем
      1. set.insert возвращает pair
      2. Полиномиальных хеш
      3. Своя хеш-таблица [код]
    6. Смотрим, какая часть долго работает
      1. Запускаем profiler [код]
      2. Замечаем, что результат зависит от наличия inline функций и уровня оптимизаций (-O0, -O1, -O2)
      3. Чтобы посмотреть, время работы конкретной части программы, можно вынести ее в функцию

Менеджеры памяти и метод "Разделяй и властвуй"

  1. Простые менеджеры памяти
    1. Мотивация
      1. Тестируем скорость работы вектора [код]
      2. Тестируем скорость работы массива
      3. Тестируем скорость работы динамического массива [код]
    2. Alloc(n), Clear() [статические вычисления]
    3. Переопределяем оператор new [vector] [array]
    4. Эксперименты про выделение памяти на C++ : "int a[(int)1e8]" не получит MemoryLimit [код]
    5. Alloc(n), DeleteLast() [рекурсивная функция]
    6. Not read p=Alloc(const), Delete(p) [список или деревья поиска]
  2. Реализации Карацубы
    1. Пишем Карацубу [код] [с аллокатором]
    2. Чтобы перемножать числа, сперва перемножаем многочлены, затем делаем переносы
    3. Если использовать систему счисления 106, умножение быстрее
  3. Сложные задачи на Разделяй и Властвуй
    1. Ближайшие точки в 2D [код]
    2. Сколько вершин в дереве находятся на расстоянии ровно k (для каждого k посчитать количество пар вершин) [код] [картинка]