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

Миша Кринкин

Ответы пользователя по тегу Алгоритмы

  • Сравнение скорости роста функций. В чем ошибка?

    @kmu1990
    Предпоследнее утверждение, вроде, тоже верно, ну просто потому, что логарифм большего числа будет больше, значит ограничение сверху никак не нарушается.
    Ответ написан
    2 комментария
    2 комментария

  • Как реализовать преобразование типа string в тип int в Java? Нужно ли это делать в рамках задачи?

    @kmu1990
    1. docs.oracle.com/javase/7/docs/api/java/math/BigInt...
    2. Что-то входные данные не сходятся с ограничениями указанными в условиях, вы точно задачу правильно привели?
    3. Все вычисления стоит производить сразу по модулю m, так как числа Фибоначчи растут очень быстро, а скорость работы с длинной арифметикой, соответственно, падает.
    4. Даже если вы поборитесь с длинными числами, ваше решение при таких больших значениях n просто не уложится во временной лимит, я полагаю, что предполагается решение использующее произведение матриц и быстрое возведение в степень.
    Ответ написан
    2 комментария
    2 комментария

  • Как создать специфичиную структуру данных для хранения большого числа записей по беззнаковому 32 битному ключу?

    @kmu1990
    Если есть возможность использовать Intel TBB, то там есть concurrent_unordered_map. Если нет возможности, то почему не реализовать unordered_map самостоятельно? В самом простом случае просто делаете shared_mutex на каждый карман, над перехешированием надо будет подумать, но с другой стороны, оно вам возможно и не понадобится, просто создайте достаточно большую таблицу с самого начала.
    Ответ написан
    Комментировать
    Комментировать

  • Как быстро выполнить топологическую сортировку дерева из списка?

    @kmu1990
    Ну например так:

    class TreeNode:
    def __init__(self):
        self.children = []
        self.name = None

    def add_child(self, child):
        self.children.append(child)

    def set_name(self, name):
        self.name = name

entries = {}
for entry in data:
    parent = entries.get(entry.ParentID, TreeNode())
    child = entries.get(entry.ID, TreeNode())
    parent.add_child(child)
    child.set_name(entry.Name)
    entries[entry.ParentID] = parent
    entries[entry.ID] = child

root = entries[RootID]


    В зависимости от используемого "словаря" (в примере entries) получаем разную сложность. Если, например, известно что ID - это числа от 0 до N, то можно использовать как словарь простой массив - тогда получаем гарантированно O(n), если пишем на C++ и в качестве словаря используем std::map или TreeMap в Java, то O(n log n).
    Ответ написан
    1 комментарий
    1 комментарий

  • Kак сортировать стрoку, которая содержит 0 и 1?

    @kmu1990
    Набросок алгоритма:

    int sort(char *line)
{
    unsigned prefix = strlen(line);
    while (prefix > 5 && !sorted(line)) {
        prefix = prefix - 1;
        if (*(line + prefix) == '0') {
            char const * at = stdchr(line, '1');
            if (at == line) {
                swap(line, line + 2);
                swap(line + 1, line + length - 1);
            }
            else {
                swap(at - 1, line + length - 1);
            }
        }
    }
    if (!sorted(line) && !bruteforce(line, prefix))
        return 0;
    return 1;
}


    Тут не хватает:

    1. Нужных заголовков
    2. Реализации функции sorted, которая возвращает 0, если строка уже отсортирована, и не 0 иначе
    3. Реализации функции swap, которая меняет местами две неперсекающиеся пары по указателям
    4. Реализации функции bruteforce, которая сортирует префикс строки длинной не более 5 символов перебором перестановок, и возвращает 0, если не удалось отсортировать префикс (например, для строки "101" или "1010"), и не 0, если удалось отсортировать.

    Инвариант алгоритма простой, prefix - длина неотсортированной части строки. Более того все символы за пределами префикса равны '1'. Мы каждый раз уменьшаем длину префикса на 1, пока не отсортируем последовательность, либо пока префикс не станет равен или меньше 5.

    Откуда берется число 5? Все последовательности длинны 5 и более можно отсортировать меняя пары, для меньших последовательностей это не всегда возможно.

    Последовательностей длинны <= 5 всего 62 (32 + 16 + 8 + 4 + 2), так что bruteforce занимает не очень много времени, но возможно есть и более разумный вариант сортировки коротких последовательностей. Вообще говоря все несортируемые последовательности легко перечислить.

    Алгоритм понятное дело не оптимальный.
    Ответ написан
    Комментировать
    Комментировать