是否有一種簡短的方法來檢測串列中帶有替代符號的最長子串列？
例如：
my_list = [-1, -0.5, 1, -3, 4, 5, 5, -1]
從-0.5到回傳 4 4？
這是我到目前為止所寫的內容，但我覺得還有更短的空間。
import numpy
my_list = [-1, -0.5, 1, -3, 4, 5, 5, -1]
# function that detects whether a list has alternate signs
# https://stackoverflow.com/questions/6451514/detect-alternating-signs
def is_alternating_signs(a):
return numpy.all(numpy.abs(numpy.diff(numpy.sign(a))) == 2)
# getting all sublists from the main list
sublists = []
for i in range(len(my_list) 1):
for j in range(i 1, len(my_list) 1):
sublists.append(my_list[i:j])
# detecting the longest sublist with alternate signs
max_list = 0
for sublist in sublists:
if is_alternating_signs(sublist) and len(sublist) > max_list:
max_list = len(sublist)
print(max_list)
uj5u.com熱心網友回復：
使用zip當前元素與下一個比較：
maxlen = 1
curlen = 1
for i, j in zip(l, l[1:]):
# if one conditions match
# increment curlen by 1
if (i < 0 and j > 0) or (i > 0 and j < 0):
curlen = 1
# break the alternative sign
# keep the highest value between maxlen and curlen
# reset curlen to 1
else:
maxlen = max(maxlen, curlen)
curlen = 1
maxlen = max(maxlen, curlen)
輸出：
>>> maxlen
4
uj5u.com熱心網友回復：
單次通關怎么辦？
def max_alt_subseq_size(seq):
last_x = seq[0]
size = max_size = 1
for x in seq[1:]:
# use the fact that x * y < 0 iff x > 0 and y < 0 or x < 0 and y > 0
if last_x * x < 0:
size = 1
else:
# once the size of the alternating subsequence is found, we need to check if it is the largest
if size > max_size:
max_size = size
size = 1
last_x = x
# check on the final subsequence to see if it is the largest
if size > max_size:
max_size = size
return max_size
my_list = [-1, -0.5, 1, -3, 4, 5, 5, -1]
max_alt_subseq_size(my_list)
# 4
uj5u.com熱心網友回復：
您可以使用 zip 來檢測交替中“中斷”的位置。然后將這些中斷組合到范圍內以找到交替值的最長連續性：
L = [-1, -0.5, 1, -3, 4, 5, 5, -1]
breaks = [i for i,(a,b) in enumerate(zip(L,L[1:]),1) if (a<0)==(b<0)]
longest = max((L[s:e] for s,e in zip([0] breaks,breaks [None])),key=len)
print(longest)
[-0.5, 1, -3, 4]
如果您只是在尋找連續的長度，您可以將 zip 結果轉換為 1 和 0 的字串，然后在 0 上拆分并測量最長的子字串：
max(map(len,"".join("01"[a*b<0] for a,b in zip(L,L[1:])).split('0'))) 1
4
uj5u.com熱心網友回復：
如果知道如何計算游程長度編碼 (RLE)，則可以使用 RLE 資訊來計算所需的值。
這將導致完全矢量化的方法。
使用以下代碼計算RLE 資訊：
import numpy as np
def rle(arr):
n = len(arr)
if n == 0:
values = np.empty(0, dtype=arr.dtype)
lengths = np.empty(0, dtype=np.int_)
else:
positions = np.concatenate(
[[-1], np.nonzero(arr[1:] != arr[:-1])[0], [n - 1]])
lengths = positions[1:] - positions[:-1]
values = arr[positions[1:]]
return values, lengths
可以通過計算陣列符號差的絕對值的 RLE 來計算所需子序列的最大長度：
def find_largest_alternating_subseq_size_np(arr):
diffs = np.abs(np.diff(np.sign(arr)))
lengths, values = rle(diffs)
return np.max(lengths[values == 2]) 1
對于足夠大的輸入，這通常比顯式回圈更快，除非顯式回圈被加速，例如使用 Numba：
import numba as nb
@nb.jit
def max_alt_subseq_size_nb(seq):
last_x = seq[0]
size = max_size = 1
for x in seq[1:]:
if last_x * x < 0:
size = 1
else:
if size > max_size:
max_size = size
size = 1
last_x = x
if size > max_size:
max_size = size
return max_size
我機器上的時間會顯示：
funcs = max_alt_subseq_size, max_alt_subseq_size_np, max_alt_subseq_size_nb
for n in (10, 100, 1000):
print(f"Input size: {n}")
ll = np.random.randint(-5, 5, n)
for func in funcs:
print(f"{func.__name__:32s}", end=" ")
print(func(ll), end=" ")
%timeit func(ll)
print()
# Input size: 10
# max_alt_subseq_size 4 6.14 μs ± 312 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
# max_alt_subseq_size_np 4 43.7 μs ± 1.71 μs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
# max_alt_subseq_size_nb 4 304 ns ± 5.75 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
# Input size: 100
# max_alt_subseq_size 6 47.6 μs ± 928 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
# max_alt_subseq_size_np 6 46.3 μs ± 900 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
# max_alt_subseq_size_nb 6 435 ns ± 9.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
# Input size: 1000
# max_alt_subseq_size 10 478 μs ± 7.35 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# max_alt_subseq_size_np 10 60.9 μs ± 1.42 μs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
# max_alt_subseq_size_nb 10 1.54 μs ± 12.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/334215.html