函数使列表尽可能不排序

Question

我正在寻找一个函数，使列表尽可能未排序。最好是Python。

背景故事：

我想检查URL的状态，看看URL是否给出404。我只是使用asyncio和请求模块。没什么花哨的。

现在我不想让服务器过载，所以我想尽量减少同时检查同一域名上的网址。我有这样的想法来排序的URL的方式是项目是彼此接近（具有相同的排序键=域名）被放置尽可能远的彼此在列表中。

以数字为例：

a=[1,1,2,3,3]  # <== sorted list, sortness score = 2
   0,1,2,3,4   # <== positions

可以不分类为：

b=[1,3,2,1,3]  # <== unsorted list, sortness score = 6
   0,1,2,3,4   # <== positions

我想说的是，我们可以通过将相等项（具有相同键=域名）之间的距离相加来计算排序分数。较高的耐酸性意味着更好的未分类。对于不安全性，也许有更好的测试方法。

列表a的排序分数为2。1的距离之和为（1-0）=1，2的距离之和为0，3的距离之和为（4-3）=1。

列表b的整洁度得分为6。1的距离之和为（3-0）=3，2的距离之和为0，3的距离之和为（4-1）=3。

url列表类似于（域、url）元组列表：

[
   ('example.com', 'http://example.com/404'), 
   ('test.com', 'http://test.com/404'), 
   ('test.com', 'http://test.com/405'), 
   ('example.com', 'http://example.com/405'), 
   ... 
]

我正在开发一个原型，它可以正常工作，但不是最优的，因为我可以找到一些更好的变体，不用手工排序。

有人想试试吗？

这是我的代码，但不太好：）：

from collections import Counter
from collections import defaultdict
import math


def test_unsortness(lst:list) -> float:
    pos = defaultdict(list)
    score = 0
    # Store positions for each key
    # input = [1,3,2,3,1] => {1: [0, 4], 3: [1, 3], 2: [2]}
    for c,l in enumerate(lst):
        pos[l].append(c)
    for k,poslst in pos.items():
        for i in range(len(poslst)-1):
            score += math.sqrt(poslst[i+1] - poslst[i])
    return score


def unsort(lst:list) -> list:
    free_positions = list(range(0,len(lst)))
    output_list = [None] * len(free_positions)
    for val, count in Counter(lst).most_common():
        pos = 0
        step = len(free_positions) / count
        for i in range(count):
            output_list[free_positions[int(pos)]] = val
            free_positions[int(pos)] = None  # remove position later
            pos = pos + step
        free_positions = [p for p in free_positions if p]
    return output_list



lsts = list()
lsts.append( [1,1,2,3,3] )
lsts.append( [1,3,2,3,1] )       # this has worst score after unsort()
lsts.append( [1,2,3,0,1,2,3] )   # this has worst score after unsort()
lsts.append( [3,2,1,0,1,2,3] )   # this has worst score after unsort()
lsts.append( [3,2,1,3,1,2,3] )   # this has worst score after unsort()
lsts.append( [1,2,3,4,5] )

for lst in lsts:
    ulst = unsort(lst)
    print( ( lst, '%.2f'%test_unsortness(lst), '====>', ulst, '%.2f'%test_unsortness(ulst), ) )

#  Orignal                score             Unsorted               score
#  -------                -----             --------               -----
# ([1, 1, 2, 3, 3],       '2.00',  '====>', [1, 3, 1, 3, 2],       '2.83')
# ([1, 3, 2, 3, 1],       '3.41',  '====>', [1, 3, 1, 3, 2],       '2.83')
# ([1, 2, 3, 0, 1, 2, 3], '6.00',  '====>', [1, 2, 3, 1, 2, 3, 0], '5.20')
# ([3, 2, 1, 0, 1, 2, 3], '5.86',  '====>', [3, 2, 1, 3, 2, 1, 0], '5.20')
# ([3, 2, 1, 3, 1, 2, 3], '6.88',  '====>', [3, 2, 3, 1, 3, 2, 1], '6.56')
# ([1, 2, 3, 4, 5],       '0.00',  '====>', [1, 2, 3, 4, 5],       '0.00')

我不是在寻找一个随机函数，我知道有一些爬虫可以管理域负载，但这是为了锻炼。

Answer 1

没有一个明显的定义是最适合你的，但是这里有一些至少很有效的东西：

1. 对列表进行排序

按照排序顺序，紧密在一起的项的索引通常只在最小的位上不同。通过颠倒位顺序，可以使相邻项的新索引在最大位上有所不同，因此它们最终会相距很远。

def bitreverse(x, bits):
    # reverse the lower 32 bits
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)
    # take only the appropriate length
    return (x>>(32-bits)) & ((1<<bits)-1)

def antisort(inlist): 
    if len(inlist) < 3:
        return inlist
    inlist = sorted(inlist)
    #get the next power of 2 list length
    p2len = 2
    bits = 1
    while p2len < len(inlist):
        p2len *= 2
        bits += 1
    templist = [None] * p2len
    for i in range(len(inlist)):
        newi = i * p2len // len(inlist)
        newi = bitreverse(newi, bits)
        templist[newi] = inlist[i]
    return [item for item in templist if item != None]

print(antisort(["a","b","c","d","e","f","g",
    "h","i","j","k","l","m","n","o","p","q","r",
    "s","t","u","v","w","x","y","z"]))

输出：

['a', 'n', 'h', 'u', 'e', 'r', 'k', 'x', 'c', 'p', 'f', 's',
 'm', 'z', 'b', 'o', 'i', 'v', 'l', 'y', 'd', 'q', 'j', 'w', 'g', 't']

Answer 2

您可以实现反向二进制搜索。

from typing import Union, List

sorted_int_list = [1, 1, 2, 3, 3]
unsorted_int_list = [1, 3, 2, 1, 3]

sorted_str_list = [
    "example.com",
    "example.com",
    "test.com",
    "stackoverflow.com",
    "stackoverflow.com",
]
unsorted_str_list = [
    "example.com",
    "stackoverflow.com",
    "test.com",
    "example.com",
    "stackoverflow.com",
]


def inverted_binary_search(
    input_list: List[Union[str, int]],
    search_elem: Union[int, str],
    list_selector_start: int,
    list_selector_end: int,
) -> int:
    if list_selector_end - list_selector_start <= 1:
        if search_elem < input_list[list_selector_start]:
            return list_selector_start - 1
        else:
            return list_selector_start

    list_selector_mid = (list_selector_start + list_selector_end) // 2
    if input_list[list_selector_mid] > search_elem:
        return inverted_binary_search(
            input_list=input_list,
            search_elem=search_elem,
            list_selector_start=list_selector_mid,
            list_selector_end=list_selector_end,
        )
    elif input_list[list_selector_mid] < search_elem:
        return inverted_binary_search(
            input_list=input_list,
            search_elem=search_elem,
            list_selector_start=list_selector_start,
            list_selector_end=list_selector_mid,
        )
    else:
        return list_selector_mid


def inverted_binary_insertion_sort(your_list: List[Union[str, int]]):
    for idx in range(1, len(your_list)):
        selected_elem = your_list[idx]
        inverted_binary_search_position = (
            inverted_binary_search(
                input_list=your_list,
                search_elem=selected_elem,
                list_selector_start=0,
                list_selector_end=idx,
            )
            + 1
        )

        for idk in range(idx, inverted_binary_search_position, -1):
            your_list[idk] = your_list[idk - 1]

        your_list[inverted_binary_search_position] = selected_elem
    return your_list

输出

inverted_sorted_int_list = inverted_binary_insertion_sort(sorted_int_list)
print(inverted_sorted_int_list)
>> [1, 3, 3, 2, 1]

inverted_sorted_str_list = inverted_binary_insertion_sort(sorted_str_list)
print(inverted_sorted_str_list)
>> ['example.com', 'stackoverflow.com', 'stackoverflow.com', 'test.com', 'example.com']

更新：给定注释，您也可以运行该函数两次。这将解开重复。

inverted_sorted_int_list = inverted_binary_insertion_sort(
    inverted_binary_insertion_sort(sorted_int_list)
)
>> [1, 3, 2, 1, 3]

Answer 3

这是一个有趣的问题。我继续使用谷歌或其他工具来解决这个问题。我把它设为一个约束优化问题，并以这种方式建模。

from collections import defaultdict
from itertools import chain, combinations
from ortools.sat.python import cp_model

model = cp_model.CpModel()
data = [
   ('example.com', 'http://example.com/404'), 
   ('test.com', 'http://test.com/404'), 
   ('test.com', 'http://test.com/405'), 
   ('example.com', 'http://example.com/405'), 
   ('google.com', 'http://google.com/404'),
   ('example.com', 'http://example.com/406'),
   ('stackoverflow.com', 'http://stackoverflow.com/404'),
   ('test.com', 'http://test.com/406'),
   ('example.com', 'http://example.com/407')
]

tmp = defaultdict(list)
for (domain, url) in sorted(data):
    var = model.NewIntVar(0, len(data) - 1, url)
    tmp[domain].append(var)  # store URLs as model variables where the key is the domain

vals = list(chain.from_iterable(tmp.values()))  # create a single list of all variables
model.AddAllDifferent(vals)  # all variables must occupy a unique spot in the output

constraint = []
for urls in tmp.values():
    if len(urls) == 1:  # a single domain does not need a specific constraint
        constraint.append(urls[0])
        continue
    combos = combinations(urls, 2)
    for (x, y) in combos:  # create combinations between each URL of a specific domain
        constraint.append((x - y))

model.Maximize(sum(constraint))  # maximize the distance between similar URLs from our constraint list

solver = cp_model.CpSolver()
status = solver.Solve(model)
output = [None for _ in range(len(data))]

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    for val in vals:
        idx = solver.Value(val)
        output[idx] = val.Name()

print(output)
['http://example.com/407',
 'http://test.com/406',
 'http://example.com/406',
 'http://test.com/405',
 'http://example.com/405',
 'http://stackoverflow.com/404',
 'http://google.com/404',
 'http://test.com/404',
 'http://example.com/404']