Состоит список только лишь из единиц, или нет?

Question

[MiheiSV]

arr - неотсортированный список рандомных положительных значений в количестве n(большинство из которых - единицы), при чем они могут повторяться
Надо выяснить, состоит список только лишь из единичек, или там есть посторонний элемент. Необходимо найти достаточно быстрое решение. То, что написано ниже не подходит, нужно быстрее. Так же преобразование arr в set не подходит, как и сумма значений массива(если вдруг такие варианты были среди возможных)

arr = [a1,a2,...,an]
if arr.count(1) == len(arr):
    ...
else:
    ...

может я туплю, но ничего более путного не придумал

Comments

[Denis Melnikov]

Нужно сделать оч быстро , но при этом , такие вещи юзать не получится ?

len(set(arr)) == 1
sum(arr) == len(arr)

Вариант линейного поиска с O(n) Тоже наверно низя ?)

for x in range(0, len(arr)):
   if arr[x] != 1:
       # не 1

что же тогда хотят от вас ?

[MiheiSV]

Denis Melnikov, set() с исходными данными занимает слишком много времени. Решение с О(n) может и подойдет, но до такого бы и я додумался, а вот вопрос в том, можно ли быстрее.
Оперативно, кстати, спасибо :)

[mayton2019]

>>> arr = [1,1,1,2,1,1]
>>> len(list(filter(lambda p : p != 1, arr))) > 0
True

[Denis Melnikov]

MiheiSV, в голову вообще ничего не лезет... кроме этих 3ех способов... Отпишите когда будет готово =) аж интересно

[MiheiSV]

mayton2019, увы, может из-за специфичности исходных данных, это решение не быстрее указанного в вопросе. Хотя очень лаконично c;

[Adamos]

MiheiSV,

Решение с О(n) может и подойдет, но до такого бы и я додумался, а вот вопрос в том, можно ли быстрее

"Бы додумался" или таки попробовал?
Быстрее чего оно должно быть? Любые извраты с функциями будут дрючить весь список. У линейной проверки есть шанс выйти раньше и не перетряхивать ненужное. Ничего быстрее в хаотичном списке и быть не может, разве что в памяти этот список представлен сплошным массивом байтов, тогда можно читать эту память словами и сверять с 0x01010101. Но это уже не для Питона методы.

[pfg21]

а если прогнать все элементы списка через побайтовое И и посмотреть что в конце получилась единица - так получится быстрее ??
понимаю, что примитивно, но чисто для единицы 00000001b будет наибыстрейший вариант.
пардон, просто для своего познания.

[MiheiSV]

Adamos, говорю же,

вопрос в том, можно ли быстрее

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

[Ипатьев]

pfg21, опять все. ЗАЧЕМ прогонять "все элементы списка"?

[mayton2019]

MiheiSV, да. Моё решение можно улучшить. На самом деле нам list/len не нужны.
Нужен фильтр и find_first. И опицональное результат. Я рассуждаю в терминах Scala/haskell.

[Denis Melnikov]

Ипатьев, не все.. в этом и прикол O(n) , стопанет на первом не нужном, просто этот первый, может быть в конце...

[Adamos]

MiheiSV, да нобелевка ему, что уж там...

[Ипатьев]

Denis Melnikov, ну где не все-то? у автора в его arr.count(1) не все? в вашем sum(arr) == len(arr) не все? в выпендрёжном len(list(filter(lambda p : p != 1, arr))) > 0 не все? у гражданина пфг21 с его побайтовым И не все?

[Denis Melnikov]

Ипатьев, первые 2 все конечно, но потом идет линейый, там возможно все... и тут ключевое ВОЗМОЖНО

[pfg21]

Ипатьев, любой произвольный элемент списка может быть не единицей. как проверить не посмотрев их все.

[Ипатьев]

pfg21, для этого надо немного подумать

[pfg21]

Ипатьев, я понимаю что поиск до первого arr[x] != 1 будет вероятно быстрее любого варианта полного перебора. но эта вероятность заранее не определима.

[Wispik]

Незнаю будет ли это быстрее, но попробуй отсортировать список и первый и последний элемент сравнить с единицей

[Denis Melnikov]

Wispik, сортировка и есть перебор всех... это не быстрее

[Adamos]

pfg21, обрывающийся перебор со 100% вероятностью будет не медленнее полного перебора.
А ничего более быстрого с неупорядоченными данными и не сделаешь.

[Wispik]

Denis Melnikov, нет сортировка, этот не перебор всех элементов.
В теории на больших данных сортировка быстрее, чем перебор, потому что сортировка делается сишной функцией

[Denis Melnikov]

Wispik, ну, тут остается только врубать профайлеры и смотреть на его выборке скорости всех методов.
Тут даже интересно, какую скорость от него требуют...

Если реально надо оч быстро, то вполне возможно и переписать на плюсы какие нить или расте с обрабткой сета дальше где то...

хз если честно=)

[Wispik]

Denis Melnikov, вот подтверждение моих слов

import time

a = [1 for x in range(10000000)]

now_time = time.time()
sorted(a)
print(time.time() - now_time)


now_time = time.time()
for _ in a:
  pass
print(time.time() - now_time)

0.0980081558227539
0.19829130172729492

[Denis Melnikov]

Wispik, разница большая... Спасибо =)

[alexalexes]

Быстрей будет, если контролировать все методы вставки в массив. Если что-то записали в него отличное от 1, то помечать этот факт.
PS: Это частный случай индексации данных (привет от индексов из СУБД).

[pfg21]

Если пошли внепитонячьи реалии, то написать на с/ассемблере мультипоточную функцию конкретного действия и забиндить в питон :)

спасибо за отличное сравнение

[Adamos]

Wispik, сортировка массива, только что заполненного одним значением - это прям всем бенчмаркам бенчмарк...
Замени-ка 1 на x % 2, например - и посмотри, как волшебны сишные функции.

[Wispik]

Adamos, это понятно, просто в контексте вопроса подразумевается, что будут одни единицы. Если все рандомные числа будут, понятно, что сортировка медленнее. Но например, если так:

a = [1 for x in range(100000000)]
a.append(5)
a.append(4)
a.append(3)
a.append(2)
a.append(2)

sorted: 0.9813046455383301
sort: 0.41123247146606445
перебор: 1.800027847290039
count: 0.10200023651123047
filter: 5.901871204376221
sum: 0.6795947551727295

сортировка все еще выгоднее. Естественно мы разговариваем в контексте вопроса, а не в абсолюте

[Adamos]

Wispik, а может быть, мы будем разговаривать в контексте вопроса, прочитав его первую строчку?

[Adamos]

Wispik, впрочем, ваш посыл "хочешь сделать быстро - делай это не на Питоне" мне вполне импонирует.

[Wispik]

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

[MiheiSV]

Adamos, действительно подразумевается список рандомных положительных чисел. Но вопрос стоит именно о "лишних" элементах среди единиц(частный случай списка). Т.е. на вход подается рандомный список, надо проверить его на наличие "лишних" элементов. set() удобен, но он медленный :C

[MiheiSV]

Если смотреть с этой стороны, то перебор вполне эффективен(т.к. список не сортирован), но задача состоит именно в поиске среди единиц, т.е. подразумевается список в большинстве из единиц.
На всякий поменяю формулировку вопроса, спасибо.

Answer 1

[Wispik]

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

arr = [....]
sorted(arr)
if arr[0] == 1 and arr[-1] == 1:
    ...

Comments

[Wataru]

Но это медленнее кода в вопросе. Там count за линию, а у вас сортировка за O(n log n)

[Wispik]

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

[Wataru]

Wispik, Но сортировка медленнее перебора.

[Wispik]

Wataru, если не брать тот случай, когда перебор заканчивается на первых итерациях, то сортировка быстрее:

import time

a = [1 for x in range(100000000)]

now_time = time.time()
sorted(a)
print(time.time() - now_time)


now_time = time.time()
for _ in a:
  pass
print(time.time() - now_time)


now_time = time.time()
if a.count(1) == len(a):
  pass
print(time.time() - now_time)

0.9765689373016357
1.7929527759552002
0.10001277923583984

[Wataru]

Wispik, какая же у вас там в питоне задница, что сортировка быстрее линейного просмотра всего списка.

[aRegius]

Только функция sorted() возвращает значение, она не изменит значение объекта in-place. Поэтому в данном случае нужно инициализировать дополнительную переменную, иначе код нерабочий. Или использовать (так как у нас list) метод sort() - он, кстати, будет и быстрее.

[Wispik]

Wataru, просто сортировка реализована встроеными функциями, которые скомпилированы на си
aRegius, да кстати sort в 2 раза быстрее выполняется

sorted: 0.9597675800323486
sort: 0.4221153259277344
перебор: 1.9935402870178223
count: 0.0982973575592041

[Wataru]

Wispik, А sum или filter какой-нибудь тогда не будет еще быстрее? Должна же быть какая-то линейная проверка всех элементов массива, реализованная на Си.

[Wispik]

Wataru, filter долго выполняется (код взял из комментариев), а sum почти как sort, но чуть медленнее:

sorted: 0.9762301445007324
sort: 0.41814494132995605
перебор: 1.971269130706787
count: 0.09899592399597168
filter: 5.726990461349487
sum: 0.6701087951660156

[Adamos]

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

[Wataru]

Adamos, Нет, все-таки, в питоне. сортировка даже массива из единиц не может быть быстрее тупо цикла (на том же уровне абстрации). Просто вот оказалось, что даже сортировка на си быстрее прохода по списку в питоне.

Однако, как и стоило ожидать, линейный перебор на си - оказался в несколько раз быстрее сортировки ( Wispik выше привел замеры - count самый быстрый).

Почему он в 6 раз быстрее sum - загадка.

[Adamos]

Wataru, например, потому, что данные "бенчмарка" тупо не успели устареть в кэше процессора.

[Вадим]

Wataru,
а так?

arr = [a1,a2,...,an]
y=next((x for x in arr if x!=1), False)
print("There are not only 1s in the array" if y else "There are only 1s in the array")

Answer 2

[Владимир Куц]

import random
import numpy as np

RANGE = 1000
data = np.ones(RANGE)
data[random.randint(0, RANGE)] = random.choice([1, 42])
data = list(data)

def check_ones1():
    result = True
    for im in data:
        if im != 1:
            result = False
            break
    return result

def check_ones2():
    return all(map(lambda x:x==1, data))

def check_ones3():
    return data.count(1) == len(data)

assert check_ones1() == check_ones2() == check_ones3()

print(check_ones1())

Если один элемент - не единица:

# False

%timeit check_ones1()
69.6 µs ± 779 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
%timeit check_ones2()
94 µs ± 936 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
%timeit check_ones3()
87.7 µs ± 633 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

если все единицы:

# True

%timeit check_ones1()
93.5 µs ± 776 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
%timeit check_ones2()
124 µs ± 374 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
%timeit check_ones3()
86.9 µs ± 566 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Answer 3

[Ипатьев]

Я не знаю, кто тот гений, который ставил эту задачу, но видимо, весь вопрос в том, чтобы догадаться, что перебирать весь массив целиком не обязательно.

result=True
for x in arr:
   if x != 1:
       result=False
       break

Comments

[MiheiSV]

Так сложились обстоятельства :D

[Ипатьев]

"так" - это в смысле знаний нету а тест пройти хочется?

[MiheiSV]

Ипатьев, в определенной степени да. Но задача "немного" сложнее заданной в вопросе, к которой у меня пока не получилось придумать лучшее решение чем я написал выше. С кем не бывает

[Adamos]

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

[mayton2019]

Sic transit gloria mundi.

Я искал решение без for/break

[Vindicar]

Ну или if any(x != 1 for x in arr):.
Должно работать так же.

Answer 4

[PavelMos]

Надо по скорости смотреть, что быстрее
можно попробовать через set это набор только уникальных значений, однако предполагается, что как минимум одна единица там должна быть - в условии сказано, что единиц большинство
res=True if len (set (arr) )==1 else False
скорость вариантов можно мерить, делая print t1=(datetime.datetime.now()) до и t2=datetime.datetime.now() после и потом print (t2-t1)
datetime модуль должен быть по умолчанию вроде установлен

Comments

[Denis Melnikov]

Вам бы ветку комментов прочесть к топику =) там уже все разобрали

Answer 5

[Вадим]

Помучился... кажется самый питоновый код будет такой:

arr = [a1,a2,...,an]
y=next((x for x in arr if x!=1), False)
print("There are not only 1s in the array" if y else "There are only 1s in the array")

Может другие подтвердят, но он должен останавливаться на любой первой не единице?

Сергей Горностаев - вам )