Как проверить, пуст ли список

Мое определение пустых списков:

a = []
a = [[], []]
a = [[], [], [[], []]]

Обычные способы неприменимы, потому что длины последних двух списков не равны 0, и они будут считаться истинными в условии if.

if a:
    print(True)    # True
#-------------------------
print(len(a) != 0) # True

Есть какие-нибудь хорошие способы проверить?

Итак, вы должны проверить это рекурсивно. если да, сколько списков вы собираетесь встроить?

Frank AK 26.10.2018 04:44

Извините, но это не определение, это всего лишь примеры. Определение найти гораздо сложнее, но давайте попробуем. Например, после a=[]; a.append(a) вы считаете a пустым?

Veky 26.10.2018 04:47

@Veky. Да, по примерам. Определение кажется довольно ясным: запрещенные элементы не допускаются.

Mad Physicist 26.10.2018 04:48

@MadPhysicist Я действительно не знаю, что вы называете "определением". На моем языке это критерий. Но не бери в голову. Конечно, мой a не содержит элементов, которые не являются списками, но [[5]] также не содержит, и, согласно OP, он «очевидно» не пуст. Я думаю, дело в том, что вы хотите сказать, что он содержит только списки пустой, и это просто циклическое определение.

Veky 26.10.2018 04:51

@Veky Я использовал "свое определение", что означает, что это определение работает только для меня, но не в этом суть ...

nochenon 26.10.2018 05:17

НО ЭТО НЕ ОПРЕДЕЛЕНИЕ! :-) Это просто примеры, которые вам подходят. Но вы считаете a выше пустым или нет?

Veky 26.10.2018 05:29

@Veky, что насчет определения: Список длины 0 пуст. Список, содержащий один или несколько пустых списков, пуст. Это достаточно точно и охватывает все примеры, опубликованные OP.

slider 26.10.2018 05:49

конечно, но по этому определению [[], [5]] пусто. Я не уверен, что ты этого хочешь. : -o

Veky 26.10.2018 20:43
2
8
2 188
6
Перейти к ответу Данный вопрос помечен как решенный

Ответы 6

Ответ принят как подходящий

Вы можете использовать функцию, которая рекурсивно проверяет элементы в подсписках:

def is_empty(l):
    return all(is_empty(i) if isinstance(i, list) else False for i in l)

так что:

print(is_empty([[], [], [[], []]]))
print(is_empty([[], [], [[], [1]]]))

выходы:

True
False

И если вы хотите обрабатывать списки, содержащие циклические ссылки, вы можете использовать набор seen, чтобы отслеживать ссылки на списки, которые видела функция, и пропускать их, когда они видны:

def is_empty(l, seen=None):
    if seen is None:
        seen = set()
    return all(seen.add(id(i)) or is_empty(i, seen) if isinstance(i, list) else False for i in l if id(i) not in seen)

так что:

a = []
a.append(a)
print(is_empty(a))
a = [1]
a.append(a)
print(is_empty(a))

выходы:

True
False

... и попробуйте его на a=[]; a.append(a), и дайте мне знать, что он говорит. ;-P На самом деле, люди, ответ намного сложнее, но пока OP не скажет, что именно они хотят (я подозреваю, что это серьезный случай проблемы XY :), мы ничего не можем сделать.

Veky 26.10.2018 05:08

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

blhsing 26.10.2018 05:11

Обновил ответ с помощью решения, которое затем проверяет циклические ссылки.

blhsing 26.10.2018 05:19

Кстати, «намного сложнее» - это с вашей стороны большое преувеличение, ИМХО.

blhsing 26.10.2018 05:25

Угловые ящики - лучший способ показать, что проблема недооценена. Одно дело - написать код, который его обрабатывает. Я просто хочу прийти к консенсусу, независимо от того, считаем ли мы его пустым или нет.

Veky 26.10.2018 05:25
all(seen.add(id(i)) or is_empty(i, seen) if isinstance(i, list) and id(i) not in seen else False for i in l) - преувеличение, хм? :-) И вот ваш второй попробуй. : -]
Veky 26.10.2018 05:28

Спасибо, ваш ответ очень подробный

nochenon 26.10.2018 05:28

@Veky Это действительно просто с логики. Не уверен, что кто-то найдет это намного более сложным.

blhsing 26.10.2018 05:30

Логически просто ?? Скажите это всем, кто изучает наборы, отличные от WF: en.wikipedia.org/wiki/Non-well-founded_set_theory Обратите внимание, что существуют четыре различные широко распространенные понятия равенства (и, соответственно, пустоты) для наборов, отличных от WF. (Конечно, списки тоже упорядочены, но я не понимаю, как это делает их меньше сложнее, чем наборы.)

Veky 26.10.2018 05:35

Я обновил ответ, добавив более развернутый тест на пустоту в случае циклических ссылок.

blhsing 26.10.2018 05:56

Чтобы проверить каждый пункт, есть простой, но полезный способ.

In [65]: a = [[], [], [[], [1]]]
In [66]: mark = []
In [67]: def recursive_check(lst, mark):
    ...:     for i in lst:
    ...:         if isinstance(i, list):
    ...:             recursive_check(i, mark)
    ...:         else:
    ...:             mark.append(i)
    ...:     return mark

А затем вы можете проверить значение глобальной метки после вызова recursive_check.

recursive_check(a, mark)

и вы можете легко проверить значение отметки, например:

if mark:
    pass

После каждого вызова, если вы запускаете его на terminal, не забывайте сбрасывать mark как пустой.

mark=[]

Чтобы упростить использование, вы можете добавить еще одну функцию, чтобы обернуть его.

In [77]: def test(lst):
    ...:     mark = []
    ...:     return len(recursive_check(lst, mark)) != 0
    ...: 

In [78]: a
Out[78]: [[], [], [[], [1]]]

In [79]: test(a)
Out[79]: True

In [80]: cc
Out[80]: [[], [], [[], []]]

In [81]: test(cc)
Out[81]: False

Думаю, вам может понадобиться рекурсивность. Попробуй это:

  def is_empty(arr, seen=None):
      # Infinite loops detection
      if seen is None:
          seen = set()
      if id(arr) in seen:
          arr.remove(arr)
      seen.add(id(arr))

      if isinstance(arr, list):
          if arr:
              return all(is_empty(b, seen) for b in arr)
          else:
              return True
      else:
          return False

По сути, все, что не является списком, означает, что ваш список не пустой. Если он находит непустой список, он начинает искать каждый элемент внутри него. Если в нем есть какой-либо элемент, кроме списка, он вернет False.

Отредактировано, чтобы избежать бесконечных циклов (спасибо @MadPhysicist!),

Попробуйте со списком, который содержит самого себя

Mad Physicist 26.10.2018 05:59

Извините, не понимаю, о чем вы. Можете прислать мне пример?

Cheche 26.10.2018 06:37
a = []; a.append(a)
Mad Physicist 26.10.2018 13:27

Довольно глупое, но, вероятно, достойное решение:

if str(a).strip('[], '):

или когда list может содержать сам себя, и это следует считать пустым:

if str(a).strip('[], .'):

Основывается на том факте, что list представлены исключительно скобками, пробелами и запятыми, но все, что они содержат (что не имеет намеренно патологического repr), имеет другой символ некоторые. list, содержащие себя, используют ... при рекурсии, поэтому их обрабатывает удаление. Итак, мы просто strip - единственные символы, видимые в пустых list, и list пустых list, и если что-то и осталось, значит, там было что-то не-listy.

А как насчет многоточия?

Mad Physicist 26.10.2018 06:30

@MadPhysicist: Синглтон Ellipsis отображается как его имя, а не три точки, потому что str из list получает repr своего содержимого, и, очевидно, repr из Ellipsis не является .... Иди разберись. Я подумал, что Ellipsis не будет считаться пустым, так что здесь это работает.

ShadowRanger 26.10.2018 13:07

Хорошо видно. +1 за сообразительность

Mad Physicist 26.10.2018 13:28

@MadPhysicist: Да, это тот вид сообразительности, который заставляет меня чувствовать себя немного брезгливым, поскольку на самом деле он решает проблему не логически, а с помощью эвристики (хотя и той, которая никогда не будет нарушена существующим кодом любой, о котором я знаю, хотя было бы тривиально создать класс для того, чтобы нарушить тест). Это почти наверняка самое быстрое решение в случае небольших и пустых list, но поскольку оно не может закоротить, оно может плохо себя вести для действительно огромных, явно непустых list, о которых более точное решение может быстро сообщить как непустые. .

ShadowRanger 26.10.2018 15:35

Это также невозможно составить; если вы хотите разрешить произвольно вложенные последовательности / коллекции / итерации, пока все такие итерации пусты, а не только произвольно вложенные list, вы не можете просто расширить набор символов strip. Тем не менее, если ваш вариант использования предназначен исключительно для работы с list, а list имеют умеренный размер (скажем, все вложения включены, сотня объектов или меньше с repr, которые не являются безумно дорогими), это довольно сложно превзойти по производительности, и невозможно превзойти по простоте кода. Мы назовем это решением Чем хуже, тем лучше.

ShadowRanger 26.10.2018 15:37

Прагматизм превыше всего

Mad Physicist 26.10.2018 17:56

Вам нужно решение, которое не только рекурсивно, но и предотвращает бесконечную рекурсию. Вот одна из таких возможностей:

def has_non_list(x):
    """ Assumes x is a list """
    seen = set()  # stash IDs since lists aren't hashable
    def check(x):
        if id(x) in seen:
            return False
        seen.add(id(x))
        for i in x:
            if not isinstance(i, list) or check(i):
                 return True
        return False
    return check(x)

Это должно быть довольно легко сделать для любой последовательности.

Более сложным / многократно используемым ответом было бы создание функции генератора, которая сглаживает вложенные list (или, для большей возможности повторного использования, произвольные итерации), что упрощает итерацию результата; если он дает что-нибудь, он непустой (и вы можете немедленно прекратить итерацию, сохраняя работу на потенциально огромных list из list), в противном случае он пуст:

def flatten(it, skip_same_list=True):
    '''Returns a generator of all non-lists in possibly nested list

    If skip_same_list is False, this will produce infinite output if a list is
    nested inside itself'''
    stack = [it]
    seen = set()
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            if skip_same_list:
                if id(item) in seen:
                    continue  # Ignores same list if seen again
                seen.add(id(item))
            stack.extend(reversed(item))
        else:
            yield item

Как только вы это сделаете, решение вашей проблемы станет тривиальным:

def my_is_empty(it, *, _sentinel=object()):
    # Two arg next returns the first item or _sentinel if no items yielded
    return next(flatten(it), _sentinel) is _sentinel

# Alternative without sentinel object:
def my_is_empty(it):
    try:
        next(flatten(it))
    except StopIteration:
        return True
    return False

Если вы хотите использовать произвольные вложенные итерации для большей применимости, а не только list, код для flatten становится более сложным, но my_is_empty остается неизменным.

По сравнению с мой другой ответ, это, очевидно, более сложный код, но он также неэвристический (поэтому типы с действительно странными repr не могут обмануть его), более пригодный для повторного использования для других целей и будет быстрее, когда большинство входных данных непустые, особенно если они большие (потому что он прекращает обработку в тот момент, когда находит подтверждение непустого статуса, не теряя времени на остальную часть list).

Другие вопросы по теме