Задать вопрос
trapwalker

Сергей П

Программист, энтузиаст
Ответы пользователя по тегу Алгоритмы

  • В чем смысл Z-буферизации, как я представляю, что сцену с парой тысяч полигонов он за 10 лет не нарисует?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    Z-буферизация нужна чтобы корректно пересекать объекты сложной формы.
    В современной графике всё сложнее, но z-буферизация никуда не денется никогда. Это просто еще один приём, чтобы достичь каких-то конкретных целей.
    Вообще нарисовать 2к полигонов - это плёвое занятие для современных видео-карт. Важно же, чтобы сквозь прорехи в листве этого вашего сотого дерева проглядывали деревья или какие-то другие объекты позади.
    Полигоны сортируются по расстоянию до камеры. Сначала рисуются наиболее удаленные, потом те, что ближе.
    Z-буфер, кстати, используется не только для определения перекрытия объектов, но и для быстрого поиска объектов под лучом.
    Ответ написан
    9 комментариев
    9 комментариев

  • Как сравнить несколько последовательностей цифр между собой?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    А какие конкретно у вас пожелания на счет скорости? У вас сложность квадратичная, 25 миллионов сравнений. Ну можно бинарные операции подключить, можно последовательности как-то обрабатывать, например сортировать. Однако в этой формулировке не ясно что не так и какие у вас получились скорости. От чего-то ж надо отталкиваться. Покажите код и вам его здесь пооптимизируют.
    А сейчас задача выглядит как "пойди туда - не знаю куда".
    Так-то можно упороться и на шейдерах это решать за счет видеокарты. Вопрос только в том, для чего все эти извращения. Если простая учебная задача - то на то она и задача, чтобы самому решать, а не на Q&A, а если практическая, то попахивает проблемами в архитектуре на более ранних этапах. Не ясна причина почему нужно быстрее, это часто повторяющаяся задача? Если так, то, быть может, имеет смысл изначально оптимизировать? Эта задача инициируется пользователем? Так может имеет смысл прибегнуть к ленивым вычислениям или посчитать заранее,чтобы не фризить интерфейсы?
    Короче, нужно больше подробностей.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоритм использовать для поиск одной из 200к+ подстроки в строке?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    BadThings, вот что могу вам предложить:
    • Разбивайте ваши строки на отдельные "слова"-претенденты для поиска. Слова ищите по отдельности в таблице.
    • Номера в таблице "нормализуйте" (не в реляционном смысле, а в смысле uppercase, удаление неоднозначных разделителей).
    • Таблицу проиндексируйте.
    • Сформулируйте стоп-критерии для слов, например по длине, наличию каких-то нехарактерных для номера символов. Для этого можно посчитать статистику по БД (min, max, set of char и т.д.).
    • Морфируйте искомые слова, например, в слове "123-0X" не ясно цифра "ноль" или буква "O" какого-то алфавита, "Икс" или кириллическая буква "Хер". Придётся строить сочетания неоднозначностей и искать их все. Но это не проблема.
    • Заведите в памяти кэш, ограниченный размером. В кэше нужно держать только слова с максимальными частотами поиска по базе. Этот кэш можно сделать персистентным и загружать в память перед поиском. Основной расчет на то, что кэшироваться будут часто встречающиеся слова, которых нет в БД.

    Таким образом из строки
    Накопитель SSD Samsung SATA III 500Gb MZ-76E500BW 860 EVO 2.5"

    "SSD", "SATA", "III", "500GB", "860", "EVO", "2.5" - не пройдут в поиск по ограничению минимальной длинны;
    "Накопитель", "Samsung" - попадут в кэш с информацией о том, что их нет в БД.
    Остальные слова, которых уже будет не так много, будут морфироваться и с логарифмической сложностью искаться в БД.
    Думаю всё будет работать просто мгновенно. В любом случае локальным персистентным кэшем несуществующих в БД слов можно закидать любые тормоза в контексте вашей задачи.
    Ответ написан
    Комментировать
    Комментировать

  • Как обойти граф?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    Если у вас граф ацикличный (ну то есть без циклов совсем), то вам подойдёт следующий алгоритм (назовём его "метод эррозии"):
    1. Удаляем из графа все узлы (кроме заданных в условии), у которых только одна связь.
    2. Повторяем П.1. пока есть что удалять.
    3. PROFIT!!! У вас в графе остался только искомый путь.

    Можно как предложили выше:
    1. Начинаем от стартового узла А. Окрашиваем его цветом i=0.
    2. Окрашиваем всех неокрашенных соседей узлов цвета i цветом i + 1, пока не покрасим целевой узел B (это теперь текущий узел x=B), тогда останавливаем раскраску.
    3. От текущего узла x (покрашенного цветом i) переходим к его соседу с цветом i-1 запоминая значения x в списке L пока i>0.
    4. PROFIT!!! У нас в L все узлы пути от B к A. Остальные узлы можно удалить из графа.
    Ответ написан
    Комментировать
    Комментировать

  • Как выполнить нормализацию адресов?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    После того, как открыли для себя сервис https://dadata.ru/, вообще перестали тратить время и деньги на собственные костыли из граблей. Сервис просто огонь.
    Для нас онлайн режим и скорость обработки не критична, поэтому мы даже уложились в бесплатный пробный тариф.
    Вроде бы у них были решения по установке их ПО в закрытом контуре, а это не что иное, как нужный вам оффлайн. Правда тут уже бесплатно не прокатит точно.

    До дадаты этот вопрос решался жутким нагромождением фильтров, регекспов с заменами и человеко-машинного совокупления.
    Общая схема годится не только для адресов, а вообще любых грязных данных:
    1. Входной датасет сохраняем в CSV и НИКОГДА не меняем.
    2. Обработка многоступенчатая. Каждая ступень состоит из фильтра и модификатора. Фильтр решает применим ли модификатор к каждой записи. Модификатор применяет свою модификацию если фильтр разрешил.
    3. Отладочный выхлоп, который показывает и позволяет быстро просмотреть полностью внесённые изменения.
    4. Каждая ступень должна делать минимальное однотипное улучшение максимально большого числа строк. Цель - каждой ступенью уменьшать разнообразие проблем, увеличивать регулярность, стандартизировать.
    5. При огромных входных датасетах можно сохранять промежуточный выхлоп, но в общем очистка должна выглядеть как пайп их последовательных ступеней обработки.
    - Очень часто бывает, что какая-то ступень незаметно ломает данные, а понимаешь это уже поздно, когда последующие ступени реализованы и отлажены, и сильно опираются на результат ломающей. Благодаря ступенчатости и иммутабельности процесса всегда можно зипнуть текущее состояние с любым предыдущим шагом и очередным фильтром заменить необходимые куски.
    - Часто бывает, что какая-то из ступеней улучшив отдельные записи убирает характерные признаки для фильтрации элемнтов для другой ступени. Благодаря такому инкрементальному процессу можно переставлять ступени местами.
    - При внесении ступенью изменения в запись. ступень должна оставлять свою сигнатуру в отдельном столбце. Удобно для поиска проблем.

    Расскажите подробнее почему не рассматривается онлайн. Заинтриговали.
    Ответ написан
    3 комментария
    3 комментария

  • Как сделать массив немножко отсортированным?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    А как считать на сколько сместился элемент? По абсолютному индексу?
    Ну и да, нужно сделать массив "полностью" или "немножко" отсортированным?
    Из постановки задачи не ясны критерии. Полностью отсортировать любой массив нельзя за указанное число шагов с указанными ограничениями.
    Нам остаётся лишь увеличивать степень упорядоченности.
    Снова возвращаемся к критериям степени упорядоченности.
    Их можно придумать несколько:
    - количество "выбивающихся" элементов
    - минимизация суммы расстояний элементов от их оптимальной позиции.
    - среднее расстояние элемента от оптимальной позиции.
    - суммарное расстояние элементов от оптимальной позиции.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоритм выборки данных из списка Python?

    trapwalker
    @trapwalker Куратор тега Python
    Программист, энтузиаст 
    s_list = [
    {'one': 1, 'two': 2, 'seven': 7, 'fix': 'price', 'number': [5, 4, 2, 3, 5, 4], 'dig': 4},
    {'one': 5, 'two': 4, 'seven': 6, 'fix': 'nix', 'number': [3, 5, 7, 2, 3, 9], 'dig': 5},
    {'one': 8, 'two': 3, 'seven': 9, 'fix': 'pix', 'number': [3, 2, 3, 1, 8, 4], 'dig': 9}
]
for i, item in enumerate(s_list):
    print('\nItem #', i, ':')    
    for key in item:
        print(key, '=', item[key])
    Ответ написан
    1 комментарий
    1 комментарий