Владимир: я просто хочу бесконечно считывать ввод данных, разбивать на строки по '\n', и что-то с этими строками делать, но делать сразу как в Python3.
aslan7470: Обращение занимает к ячейке занимает константное время, я же по индексу обращаюсь. А вот копирование да, не учел, так что в общем я думаю вы правы O(n).
Я думаю там задача стоит не в ужимании словаря или структурах данных, а в том чтобы выявить закономерности в этих словах и потом по этим закономерностям опредлеять слово это или нет. К примеру если в строке нет согласных, то это не слово. И так несколько проверок. В конце алгоритм должен выдать вероятность того, что это слово.
aslan7470: Решил, спасибо. Использовал три массива один хранит концы последовательностей, второй их индексы, трейтий все предыдущие элементы. А по-поводу решения с хранением последовательностей в массива (массив массивов). Вставка делается за линейное время, но я ее ни разу не делал, я делал присваивание по индексу, а это время константное, так что общее - тоже O(nlogn), вот только память n^2
aslan7470: делаю не вставку, а замену, [[6], [6,4], [6,4,4]] далее идет скажем 5, бинарный поиск указывает что нужно поставаить на 0 индекс. я иду к 0 индексу и вижу там последним элементом 6, 6 меньше 5 значит я копирую этот массив и прибавляю к нему 5, получаю [6,5] и заменяю со следующим эелементом, получаю - [[6], [6,5], [6,4,4]]
aslan7470: Опять пример данно - [4, 4, 3, 4, 6, 5, 3] для него наибольшая невозрастающая последовательноть - [4,4,4,3], а если я буду хранить только последние элементы, то список моих подпоследовательностей после выхода из цикла будет - [6,5,4,3] и что-то я не пойму как мне из этого восстановить нужную последовательность
aslan7470: т.е. хранить только последние элементы для каждой последовательности, возможно, но я не уверен что смогу потом восстановить по последнему индексу и длине всю последовательность
aslan7470: Получается, длины не могут совпадать и каждая следующая на одну больше, длина соотвествует индексу массива temp +1, т.е. в temp[0] всегда хранится последовательность длины 1 и так далее. Делаю это с помощью условий после сеарча. Одним словом алгоритм корректен, но жрет слишком много памяти и с этим я пока не могу справиться. А по поводу вашего предыдущего предложения - немного не понял, что вы мне предлагаете хранить вместо подпоследовательностей для того чтобы получить O(n), не могли бы на примере показать, а в map не вижу необходимости мой массив temp выполняет ту же функцию.
Pan Propan: ну это смотря где хранится ваше время, засунете в юзера, не будет, в какой-нибудь профайл - будет если он больше не для чего не используется, в любом случае и то, и то можно закешировать
Нет, не в любой, а только в конкретный, самый длинный из подходящих, для [[6], [6,5], [6,4,4]] при добавлении 3, я делаю такой [[6], [6,5], [6,4,4], [6,4,4,3]]. Добавление в список в Python - O(1), просадку уже нашел была в - tuple(x[-1] for x in temp, нужно было вынести из цикла и изменять на каждой итерации, но теперь я по памяти не вкладываюсь(
aslan7470: Все верно. Объясню на примере, в чем идея. Нужно найти наибольшую невозрастающюю последовательность, т.е. 4,3 или 4,4 и т.д. Если у нас есть массив А[1,2,3,3,2], на первой этирации наши потенциальные максимальные подпоследовательности - А[0], на второй - A[1], так как A[1]>A[0] и не может существовать последовательности начинающейся на A[0], которая была бы длинней, чем последовательность начинающаяся на A[1], на 3-й A[2] по аналогичной причине, на 4-й A[2,3] т.к A[2]==A[3], а значит любая последовательность, начинающая на A[2], будет длиннее чем с A[3] и на 5-й A[2,3], A[2,3,4] т.к. A[3]>A[4], а это значит, что A[2,3] еще есть шансы стать максимальной подпоследовательнсотью
В temp я храню подпоследовательности, для которых индекс соответсвует длинне этой последовательности -1, а последний элемент каждой подпоследовательности не больше следующей подпоследоватльности т.е. - [[6], [6,5], [5,4,3], [5,4,3,3]]. Каждый новый элемент из l либо продолжает одну из последовательностей, либо начинает новую. Скорость проход по l за время n, что делать c новым элементом - это поиск в temp за log k. Совокупная скорость - n log n, какая и должна быть, но у меня видимо большая константа. На сях решение - e-maxx.ru/algo/longest_increasing_subseq_log, но тут уже я не могу понять код.
kaato: Я к тому, что POST запрос на компанию подразумевает, что юзера нет, значит его нужно сделать. Если вы создадите отдельный url, POST для компании останется не используемым, поэтому первое решение создание юзера и компании на пост урле компании, кажется мне более разумным.