当前位置: 首页 > 面试题库 >

锁组合,用于动态锁大小

羊舌和安
2023-03-14
问题内容

下面,我将给出两个具有不同尺寸值的示例。

锁1

# numbers are the shown values on the so in this case: 0,1,2
numbers = 5
# fields are those things i can turn to change my combination
fields = 4

所以我对我所有的期望是

0   0   0   5
0   0   1   4
0   0   2   3
0   0   3   2
0   0   4   1
0   0   5   0
0   1   0   4
0   1   1   3
0   1   2   2
0   1   3   1
0   1   4   0
0   2   0   3
0   2   1   2
0   2   2   1
0   2   3   0
0   3   0   2
0   3   1   1
0   3   2   0
0   4   0   1
0   4   1   0
0   5   0   0
1   0   0   4
1   0   1   3
1   0   2   2
1   0   3   1
1   0   4   0
1   1   0   3
1   1   1   2
1   1   2   1
1   1   3   0
1   2   0   2
1   2   1   1
1   2   2   0
1   3   0   1
1   3   1   0
1   4   0   0
2   0   0   3
2   0   1   2
2   0   2   1
2   0   3   0
2   1   0   2
2   1   1   1
2   1   2   0
2   2   0   1
2   2   1   0
2   3   0   0
3   0   0   2
3   0   1   1
3   0   2   0
3   1   0   1
3   1   1   0
3   2   0   0
4   0   0   1
4   0   1   0
4   1   0   0
5   0   0   0

我的第二把锁具有以下值:

numbers = 3
values = 3

所以我所期望的像这样

0   0   3
0   1   2
0   2   1
0   3   0
1   0   2
1   1   1
1   2   0
2   0   1
2   1   0
3   0   0

我知道这可以用类似方法完成itertools.permutations,但是我想通过建立行而不是通过使我的RAM超载来生成行。我发现最后两行总是以相同的方式建立。所以我写了一个为我构建的函数:

def posibilities(value):
    all_pos = []

    for y in range(value + 1):
        posibility = []
        posibility.append(y)
        posibility.append(value)

        all_pos.append(posibility)

        value -= 1

    return all_pos

现在,我想以某种方式使函数中的其他值动态适合,例如Lock-2现在看起来像这样:

0   posibilities(3)
1   posibilities(2)
2   posibilities(1)
3   posibilities(0)

我知道我应该使用while循环等等,但是我无法获得动态值的解决方案。


问题答案:

可以 递归执行此操作,但是通常最好避免在Python中进行递归,除非您 确实
需要,例如在处理递归数据结构(例如树)时。标准Python(又名CPython)中的递归效率不高,因为它无法进行尾部调用消除。此外,它还应用了递归限制(默认情况下为1000个级别,但用户可以修改)。

要生成的序列称为弱组合,而Wikipedia文章提供了一种简单的算法,该算法易于在标准itertools.combinations函数的帮助下实现。

#!/usr/bin/env python3

''' Generate the compositions of num of a given width

    Algorithm from 
    https://en.wikipedia.org/wiki/Composition_%28combinatorics%29#Number_of_compositions

    Written by PM 2Ring 2016.11.11
'''

from itertools import combinations

def compositions(num, width):
    m = num + width - 1
    last = (m,)
    first = (-1,)
    for t in combinations(range(m), width - 1):
        yield [v - u - 1 for u, v in zip(first + t, t + last)]

# test

for t in compositions(5, 4):
    print(t)

print('- ' * 20)

for t in compositions(3, 3):
    print(t)

输出

[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 0, 3, 2]
[0, 0, 4, 1]
[0, 0, 5, 0]
[0, 1, 0, 4]
[0, 1, 1, 3]
[0, 1, 2, 2]
[0, 1, 3, 1]
[0, 1, 4, 0]
[0, 2, 0, 3]
[0, 2, 1, 2]
[0, 2, 2, 1]
[0, 2, 3, 0]
[0, 3, 0, 2]
[0, 3, 1, 1]
[0, 3, 2, 0]
[0, 4, 0, 1]
[0, 4, 1, 0]
[0, 5, 0, 0]
[1, 0, 0, 4]
[1, 0, 1, 3]
[1, 0, 2, 2]
[1, 0, 3, 1]
[1, 0, 4, 0]
[1, 1, 0, 3]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3, 0]
[1, 2, 0, 2]
[1, 2, 1, 1]
[1, 2, 2, 0]
[1, 3, 0, 1]
[1, 3, 1, 0]
[1, 4, 0, 0]
[2, 0, 0, 3]
[2, 0, 1, 2]
[2, 0, 2, 1]
[2, 0, 3, 0]
[2, 1, 0, 2]
[2, 1, 1, 1]
[2, 1, 2, 0]
[2, 2, 0, 1]
[2, 2, 1, 0]
[2, 3, 0, 0]
[3, 0, 0, 2]
[3, 0, 1, 1]
[3, 0, 2, 0]
[3, 1, 0, 1]
[3, 1, 1, 0]
[3, 2, 0, 0]
[4, 0, 0, 1]
[4, 0, 1, 0]
[4, 1, 0, 0]
[5, 0, 0, 0]
- - - - - - - - - - - - - - - - - - - - 
[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]

FWIW,以上代码可以compositions(15, 8)在运行于Python 3.6或Python 2.6的旧2GHz
32位计算机上,在约1.6秒内生成170544个序列。(时序信息是通过使用Bashtime命令获得的)。

FWIW,这是user3736966从此答案中获取的递归版本。我已经对其进行了修改,以使用与代码相同的参数名称,使用列表而不是元组,并与Python
3兼容。

def compositions(num, width, parent=[]):
    if width > 1:
        for i in range(num, -1, -1):
            yield from compositions(i, width - 1, parent + [num - i])
    else:
        yield parent + [num]

出乎意料的是,此版本比原始版本快一点,大约要花1.5秒compositions(15, 8)

如果您的Python版本不懂yield from,您可以执行以下操作:

def compositions(num, width, parent=[]):
    if width > 1:
        for i in range(num, -1, -1):
            for t in compositions(i, width - 1, parent + [num - i]):
                yield t 
    else:
        yield parent + [num]

要按降序生成构图,只需将range调用调换即即for i in range(num + 1):

最后,这是一个不可读的单行版本。:)

def c(n, w, p=[]):
    yield from(t for i in range(n,-1,-1)for t in c(i,w-1,p+[n-i]))if w-1 else[p+[n]]

作为一个顽固的修补匠,我无法阻止自己制作另一个版本。:)这只是原始版本combinations,以及itertools文档中列出的代码。当然,实数itertools.combinations是用C编写的,因此它比文档中所示的等效Python代码运行得更快。

def compositions(num, width):
    r = width - 1
    indices = list(range(r))
    revrange = range(r-1, -1, -1)
    first = [-1]
    last = [num + r]

    yield [0] * r + [num]
    while True:
        for i in revrange:
            if indices[i] != i + num:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield [v - u - 1 for u, v in zip(first + indices, indices + last)]

这个版本比原始版本慢50%compositions(15, 8):在我的机器上大约需要2.3秒。



 类似资料:
  • 问题内容: 我在这里思考:如果您有2个线程执行需要同步的FAST操作,那么非阻塞方法不是比阻塞/上下文切换方法更快/更好的方法吗? 非阻塞的意思是: while(true){如果(checkAndGetTheLock())中断;} 如果您有太多线程在锁中循环,我唯一想到的就是饥饿(CPU耗尽)。 如何平衡一种方法与另一种方法? 问题答案: 以下是 Java Concurrency in Pract

  • 我想为strerror\u r调用创建线程本地缓冲区,并编写自己的线程安全字符*my\u strerror(int),它将使用线程本地缓冲区并调用strerror\r。 当阅读R. Stevens在Unix环境高级编程中关于pthread_getspecific()的例子时,我觉得差异-为什么在下面的例子中使用互斥锁? 书中的例子:

  • 问题内容: 寻找有关 fcntl 和 lockf 的 优点 和 缺点 的信息以进行文件锁定。例如,哪个更适合用于便携性?我目前正在编写linux守护程序,并想知道哪种守护程序更适合用于执行互斥。 __ __ 问题答案: lockf和fcntl有什么区别: 在许多系统上,库例程只是的包装。也就是说,提供了该功能的子集。 资源 但是,在某些系统上,并且锁是完全独立的。 资源 由于它取决于实现,因此请确

  • 我有以下类层次结构: 我正在尝试读取并锁定一个具体实例,以便其他事务无法读取它,使用hibernate。 现在的函数: 正在工作-为刷新操作生成“SELECT for UPDATE”语法。 refresh()和get()函数之间的不同之处在于get()函数使用外部左联接来选择具体对象,而refresh()使用内部联接来选择具体对象。 在悲观锁定的上下文中,这些连接之间有区别吗?

  • 嗨, 我们有一个应用程序(J2EE/Hibernate/JPA),其中有几个用户在一个公共实体上执行操作。 句子是单独的实体 几个用户同时更新同一句话的几率很低 在这种情况下,其中一个用户可以收到消息“对不起另一个用户试图编辑相同的句子” 到目前为止还不错。 但是现在,我们已经为这个应用程序添加了后台进程(相当快的进程)。他们经常做出改变(假设它将一个词的出现替换为另一个词)。 这是不能接受的向用

  • 本文向大家介绍互斥锁死锁,包括了互斥锁死锁的使用技巧和注意事项,需要的朋友参考一下 死锁可以在使用互斥锁的多线程Pthread程序中发生。让我们看看它如何发生。未锁定的互斥锁由pthread_mutex_init()函数初始化。 使用pthread_mutex_lock()和pthread_mutex_unlock()获取并释放互斥锁。如果线程尝试获取锁定的互斥锁,则对pthread_mutex_