Ответы пользователя по тегу Алгоритмы
  • В чем я ошибся в решении задачи VK EDUCATION?

    @codingoleg
    Ваше решение технически верное, но имеет 2 недостатка, особенно для больших массивов и/или частых операций.
    Во-первых, вы создаёте копию массива для итерации (arr[::-1]), который занимает памяти столько же, сколько оригинальный массив. Во-вторых, вы удаляете элементы из массива по значению (remove), а не по индексу (del), что существенно замедляет выполнение. Рекомендую ознакомиться, как массив устроен под капотом и временную сложность добавления, вставки, изменения и удаления в него. Отсюда также будет понятно, почему одновременная итерация в прямом порядке с помощью цикла for и удаление элементов из массива - это плохая идея. Вот вам 4 функции с бенчмарками, из которых первая ваша:
    import random
    import time
    
    
    def func(arr, el):
        for i in arr[::-1]:
            if i == el:
                arr.remove(el)
        return len(arr)
    
    
    def remove_reverse(arr, el):
        for i in reversed(arr):
            if i == el:
                arr.remove(el)
        return len(arr)
    
    
    def del_by_index_reverse(arr, el):
        for i in reversed(range(len(arr))):
            if arr[i] == el:
                del arr[i]
        return len(arr)
    
    
    def del_by_index_while(arr, el):
        i = 0
        while i < len(arr):
            if arr[i] == el:
                # Удаляем значение по индексу и не сдвигаем указатель i
                del arr[i]
            else:
                i += 1
        return len(arr)
    
    
    # Создаем массив из 100000 случайных цифр от 0 до 9 и сделаем по копии для каждой функции
    arr1 = [random.randint(0, 9) for num in range(100_000)]
    arr2 = arr1[:]
    arr3 = arr1[:]
    arr4 = arr1[:]
    el = 5
    
    start = time.perf_counter()
    print(func(arr1, el))
    print(time.perf_counter() - start)
    
    start = time.perf_counter()
    print(remove_reverse(arr2, el))
    print(time.perf_counter() - start)
    
    start = time.perf_counter()
    print(del_by_index_reverse(arr3, el))
    print(time.perf_counter() - start)
    
    start = time.perf_counter()
    print(del_by_index_while(arr4, el))
    print(time.perf_counter() - start)
    Ответ написан
    Комментировать