дали кое какие задание и одно из них мне непонятно. Просто объясните что от меня хотят, писать за меня не надо.
Дано: список dict-объектов вида вида {"key": "value"}, например [{"key1": "value1"}, {"k1": "v1", "k2": "v2", "k3": "v3"}, {}, {}, {"key1": "value1"}, {"key1": "value1"}, {"key2": "value2"}].Напишите функцию, которая удаляет дубликаты из этого списка. Для примера выше возвращаемое значение может быть равно [{"key1": "value1"}, {"k1": "v1", "k2": "v2", "k3": "v3"}, {}, {"key2": "value2"}].Обязательное условие: функция не должна иметь сложность O(n^2).
list(set(твое входное говно))
жопу свою ставишь, что set входного говна не O(n2)?
Что, пограмисты изобрели себе ммр? А то хуйня какая-то, джуны-сеньоры, ничего не понятно, а так приходишь: "У меня 8700 ммр в питоне" и всем сразу понятно всё.
да мне похуй, я кодмакака
for j in x:
if i == j:
del x[x.index(j)]
#[{'key1': 'value1'}, {'k1': 'v1', 'k2': 'v2', 'k3': 'v3'}, {}, {}, {'key1': 'value1'}, {'key1': 'value1'}, {'key2': 'value2'}]
#[{'k1': 'v1', 'k2': 'v2', 'k3': 'v3'}, {}, {'key2': 'value2'}]
В чем он неправ?
>>261710098
>>261710382
кстати лол, оп, ебани какой нибудь самый мега уебанский алгоритм O(nn!). не, ну а хуле, не O(n2) же
Создаешь в функции пустой лист, делаешь проход по входному листу, если элемент входного листа новый - пихаешь во внутренний лист. Скорее всего это будет O(n^2), поэтому делай рекурсией, лол.
>функция не должна иметь сложность O(n^2)
Хотя о чём это я, сложности какие-то. Ебаните новый кукурайзен, и будет считать нормально, ёпта!
Бля да в словарь эту хуйню пихаешь и все удаляется ебать
xi=0
xj=1
for i in x:
xi=xi+1
for j in x:
if i == j and xi!=xj:
xj=xj+1
del x[x.index(i)]
print(x)
T ГЕНИЙ?
> делай рекурсией, лол
Будет то же самое.
>>261711188
>>261710444
Школоло-эксперты, вы хоть знаете, что такое O большое?
Как вообще понять что такое сложность алгоритма? Для этого надо знать дискретку или это самостоятельная дисциплина?
Раз такой умный возьми да напиши
А что если просто рассортировать массив по размеру словарей, а потом заебенить бинарный поиск? Уже как минимум будет меньше n^2
Напишу в нескольких вариантах-так что твои работодатели охуеют,за все 5к на карту
В смысле? Что написать? Я спросил, как понять, т.е. что читать надо, что знать надо чтобы познать эту дисциплину?
Например?
Отдельная дисциплина, "теория сложности"
лист в сет за o(n) перекидывается, мань. сет в лист еще за один n
ТОЛСТО
Куда собеседование то? Сомневаюсь что в реальном коде будет такой дурацкий шмоток словарей и да ещё их сортировка будет требовать дополнительной оптимизации. Это же всё на стадии организации данных пресекается.
Хуй его знает, зовут django писать вроде как. ВОпросы по джанго я закрыл
а тут это
Загугли timsort и binary search. Если ты не тупой, то сделаешь все по гайдам, а, возможно, и как-то упростишь.
https://habr.com/ru/company/otus/blog/565640/
Суть такова: сортируешь по тимсорту, а потом этот самый лист пробегаешь по бинарному поиску.
Выходит время n * log ^ 2 (n), если я не ошибаюсь.
new_dict = []
for i in old_dict:
if i not in new_dict:
new_dict.append(i)
return new_dict
ЧТО ДУМОЕТЕ?
оп
Тебе написали - кидай в сет, это самое быстрое решение из всех
>new dict
>list
Мы вам перезвоним
Анон, я думал тебе правда нужна помощь, а ты троллишь
>Просто объясните что от меня хотят
От тебя хотят избавиться таким способом.
>функция не должна иметь сложность O(n^2)
Можешь написать йоба функцию, которая будет еще медленнее и ржать им в лицо.
Либо тебя реально наебывают, либо ты собеседуешься у таких же даунов. Тебе минимум нужно посмотреть весь массив это уже n. Дальше тебе нужно хранить информацию об уникальных копиях и сверяться с ней каждый раз. Единственный тут вариант это создать второй массив и двоичным поиском проверять есть твой объект в нем или нет. Если его там нет, то у тебя сразу будет отсортированное место вставки, тогда ты часть массива двигаешь вправо, и вписываешь туда новый объект. Но в любом случае это около n^2, потому что тебе нужно n раз поискать log2(n) (на самом деле меньше, потому что n = [0; n]) + переписать массив в худшем случае n раз вправо, а это опять читать элементы и записывать элементы.
Короче, тебя сплавляют методично.
Так еще собеседования не было
это тип опросник небольшой
Алсо, второй вариант, это ты сортируешь за n × log(n) массив и дальше из него линейно выкидываешь в новый массив уникальные копии, это будет n + n × log(n).
Еще один со скиллбокса, которому не рассказали про сеты
delete_dub(x)
print(datetime.now() - start_time)
#0:00:00
И чо какого хуя?
Так политкорректность, привыкай.
>>261713190
Мань, ты знаешь сложность поиска в сете? Или ты думаешь он магически и бесплатно сохраняет уникальные копии?
const result = [...new Set(
list.map(item => JSON.stringify(item))
)].map(json => JSON.parse(json)
Моя ЗП $5000, задавайте ответы.
Если сет не устроит то
const obj = list.map(item => JSON.stringify(item))
.reduce((acc, curr) => (acc[curr] = true, acc), {})
const result = Object.keys(obj).map(json => JSON.parse(json))
Собеседования какие-то. Почему до сих пор не запилили какой-нибудь сайт или приложение, где просто в сидят все программисты и пишут код. Потом дружно делят деньги между собой.
Что?
Для особо умных: в жс строковые ключи в объекте сохраняются в порядке добавления и он гарантируется.
>const obj = list.map(item => JSON.stringify(item))
>.reduce((acc, curr) => (acc[curr] = true, acc), {})
>const result = Object.keys(obj).map(json => JSON.parse(json))
Это жи не пайтон нихуя
new_l = []
for i in l:
if i not in new_l:
new_l.append(i)
return new_l
Так чо?
>сложность O(n^2).
Поясните это.
Не погромизд.
Блядь, ты правда такой тупой?
https://devenum.com/how-to-remove-duplicates-list-of-python-dictionaries/
Первая ссылка в гугле по запросу "python duplicates in list of dicts fastest way to remove". Пиздос вы пориджи деградировали.
мимодевопс
Господи, какой же ты тупой, я просто хуею.
set(лист) - o(n) на проход листа o(1) на добавление говна в сет (хуевый амортизированный o(n)). o(n) + o(1) (или o(n)) дает o(n).
list(сет) - o(n).
o(n) + o(n) сколько будет?
давай загуглю за тебя
https://ru.wikipedia.org/wiki/Теория_сложности_вычислений
А теперь поясни так, чтобы понял не погромизд. На пальцах.
мимопо
Если только пальцем в жопу. Нельзя так просто взять и объяснить квантовую механику языком, который был придуман одной обезьяной, чтобы объяснить другой обезьяне на какой пальме висят бананы.
Удали миллион объектов и проверь.
Ну смари, у тебя есть коллекция из n элементов.
Чтобы пройтись по ней один раз, ты должен выполнить n процедур. Если ты для каждого из элементов проходишься ещё раз по всем остальным n элементов, то ты вызываешь эту процедуру n * n раз. Это сложность O(n^2). То есть с увеличением числа n количество выполняемых процедур растёт как последовательность {n^2}.
for i in l:
if i not in new_l:
То есть тут я так или иначе пройдусь n^2?
Да. Ну я не уверен в реализации оператора in в питоне, но теоретически он проходится по всему массиву (в худшем случае, сложность всегда считается по худшим случаям), и сравнивает твой элемент со всеми остальными n элементами.
Квантовые сказки это бред.
Что у опа за условие, что можно на каждый байт удваивать время работы? Типа вообще похую?
u = {}
for d in dano_: # O(n)
strd = str(d) # O(1)
if not strd in u: # O(1)
u[strd] = d # O(1)
otv = [
v
for k,v in u.items() # O(n)
]
# O(n1112) = O(2n)
return otv
звездочки в последнем комментарии похерились.
крч сложность O(2n)
python 3.9. порядок элементов словаря сохраняется и гарантируется
for i in l:
if i not in new_l:
new_l.append(i)
return new_l
Как я понял будет: я беру 7 элементов
и делаю цикл в 7 тактов
каждый такт я сравниваю свой новый Лист с текущим значением
это получается: N+N разве нет?
Что я имею ввиду: первый такт у меня пустой лист , значит IN не будет проходится по листу
второй такт он пройдет 1 элемент
третий такт 2 элемента и тд
Это получается O(n+(n-1)) ВЕРНО?
Спасибо ОП, сегодня было много тредов про вкат в айти, и я даже преисполнился немного, что решил продолжить изучение Питона, и тут ты с тредов, где аноны гении решают задачу, суть которой я буквально не понимаю, что лишний раз убедило меня в том, что наверное вот это вот все, вся эта абстрактная хуйня, не для меня, и мне стоит начать изучать что либо другое. Спасибо тебе анон, спасибо вам аноны, что я немного разобрался в себе.
Абу благословил этот пост.
в чем он не прав?
>>261714713
>>261714573
Люди, вы правда думаете. что оператор in волшебным образом возвращает ответ, а не создает новый цикл???
а узнать то как?
для ключей словаря - нет. В том то и фишка словаря.
Чем плох этот вариант?
Константы приводятся к 1
Сложность оценивается зависимостью операций от переменных, а не постоянных величин.
какая там на самом деле сложность?
То есть даже если взять логарифм по базе 2 или по базе 10 - для оценки сложности разницы нет, потому что график функции растет одинаково.
O(n)
т.е. задача решена?
>if i not in new_l:
Как язык делает это без цикла, объясните деду, я только паскаль знаю.
python
Это залупа все под капотом делает
а под капотом там c++
Да, даже есть формула
log a (n) = log b (n) / log b (a) , это показвает, что можно выбрать абсолютно любое подлогарифмическое число.
>>261715241
То есть даже на большом количестве входных данных, пайтон моментально вернет результат?
как правильно ответить на этот вопрос
Какие способы параллельной обработки запросов на Django вы знаете?
> данных пайтон
быстрофикс
не моментально.
ключи словаря - HashMap. Время поиска по ней не зависит от кол-ва элементов - константно. Т.е. O(1)
Пошел нахуй выродок брухлявой проститутки. Чтобы вы все вайтишники горели в аду.
Запомни меня сука, я тот кто завалит тебя и таких как ты на собеседовании спрашивая про ебучие обходы деревьев и мне будет расрать что ты не будешь заниматься этим на работе.
Моя задача - чтобы ты сдох от голода мразь
меня пошлют нахуй?
оп
Что ж, мне на лекциях по шарпу про это не рассказывали.
В любом случае, не думаю, что код, который может написать любой школьник, ожидают на собесе
Временная сложность это предел роста времени работы алгоритма при стремлении к бесконечности размера исходных данных.
Соответственно, алгоритмы бывают логарифмическими (при поиске в бинарном дереве обычно бывает именно логарифмическая сложность), полиномиальными, экспоненциальными и т.д. Здесь мы дрочим на медленность, т.е. если мой алгоритм линейный, а твой экспоненциальный, то ты обосрался.
n это примерное количество элементов с которыми надо что-то сделать
O(log(n)) или O(n^2) это сколько раз прийдётся использовать каждый из них. Идеал - O(1), наихудший вариант (примерно) - O(n*n!)
Чтоб понять, насколько это плохой случай - https://ru.wikipedia.org/wiki/Bogosort
сортируй и удаляй один из соседних одинаковых. n log n
пасрал на вайтишку ебаную.
>так, чтобы понял не погромизд. На пальцах
Средний видишь?