算法以大多数经济努力实现合理的结果



假设看书时需要处理六种问题,
我具体说明如下:

while True:
if encounter A :
handle A
#during handling the problem, it might spawn new problems of
#A, B, C, D, E,
produce  (A,B..E or null)
continue
if B occurs:
handle B
#during hanlding the problem, it might spwan new problems
#A, B, C, D, E,
produce  (A,B..E or null)
continue
if C happens:
handle C
produce (A,B..E or null)
continue
...
if there are no problmes:
break

假设我有 3 个问题,上面的程序可能会在第一个问题上无限循环,
而永远不会触及第二个。

举个例子,我正在看一本书,">
问题A"被定义为遇到一个"新词",处理它就是查找字典。
抬头时,我可能会想到另一个新词,另一个又一个。
在这种情况下,我永远不会读一本书的一句话。

作为解决方案,我引入了一个容器来收集问题,对它们进行值加权,
然后确定执行哪一个。

def solve_problems(problems)
problem_backet = list(problems)
while True:
if problem_backet not is null:
#value-weighted all the problem 
#and determine one to implement
value_weight problems
problem = x
if problem == A:
handle A
problem_backet.append(new_problem)
continue
if problem == B:
handle B
problem_backet.append(new_problem)
continue
...
if problem_backet is null:
return 

我试着寻找灵感,提高效率。

def solve_problems(problems):
global problem_backet
problem_backet = list(problems)
value_weight problems
problem = x
if problem == A:
handle A
problem_backet.append(new_problem)
solve_problems(problem_backet)
if problem == B:
handle B
problem_backet.append(new_problem)
solve_problems(problem_backet)
if problem == C:
handle C
problem_backet.append(new_problem)
solve_problems(problem_backet)
...
if problem_backet is null:
return

同样,value_weighted过程消耗了大量的精力和时间。

如何在适当的算法中解决这样的问题?

"问题A"被定义为遇到一个"新词",处理它是查找字典。 抬头时,我可能会遇到另一个新词,一个又一个。 在这种情况下,我永远不会读一本书的一句话。

看起来它最终会阅读句子,因为新单词的数量受到字典大小的限制。总的来说,这对我来说听起来不错,除非有一些其他一些没有明确提到的限制,比如在有限的时间内完成句子阅读。

如何在适当的算法中解决这样的问题?

好吧,如果没有"限时"限制,您的原始算法几乎是完美的。为了使它在整体性能方面做得更好,我们可能会先处理所有问题A,然后再转到B等等。它将提高我们算法的数据局部性和整体性能。

但是,如果有"有限时间"的限制,我们最终可能会在这段时间内阅读完整的句子(没有完全理解),或者最终阅读句子的一部分(完全理解该部分)或介于两者之间的内容(如@Lauro Bravar所建议的那样)。

从上面的例子中,我们不太清楚我们如何做value_weight,但这类问题的正确名称是优先级队列。有多种算法和实现,请查看维基百科页面了解详细信息:https://en.wikipedia.org/wiki/Priority_queue

你可以做几件事来解决这样的问题。

其中之一是以机器学习风格设置"最大迭代次数"或"最大工作量"的值,您可以将其投资于阅读书籍。因此,您最多只能执行(处理)多个操作,直到达到限制。此解决方案将如下所示:

while(effortRemaining > 0){
# Do your actions
}

您执行的操作应该是根据您需要定义的某些指标报告更多收益/更少工作量的操作。

当您执行某个操作(句柄)时,您可以从effortRemaining中减去该操作的成本/工作量,然后继续您的流。

你已经有了算法(在Andriy的帮助下,用于优先级队列),但你缺乏设计。当我看到您的多个if检查问题类型时,我想到多态性。 为什么不试试OOP?您有两个对象要定义:问题和优先级队列。幸运的是,优先级队列是在heapq模块中定义的。让我们关注这个问题: 在其核心定义中,它被处理并可以与其他问题进行比较(它或多或少是紧急的)。请注意,在 OOP 原则的指导下,我不谈论问题的结构或实现, 但仅限于问题的功能

class Problem()
def handle(self, some args): # we may need a dictionary, a database connection, ...
...
def compare(self, other):
...

但是你说,当一个问题被处理时,它可能会给队列增加新的问题。因此,让我们为handle的定义添加一个精度:

def handle(self, queue, some args): # we still may need a dictionary, a database connection, ...
...

在Python中,compare是一种名为__lt__的特殊方法,表示"低于"。(您还有其他特殊的比较方法,但__lt__在这里就足够了。

下面是一个基本的实现示例:

class Problem():
def __init__(self, name, weight):
self.__name = name
self.__weight = weight
def handle(self, queue):
print ("handle the problem {}".format(self))
while random.random() > 0.75: # randomly add new problems for the example
new_problem = Problem(name*2, random.randint(0, 100))
print ("-> Add the problem {} to the queue".format(new_problem))
heapq.heappush(queue, new_problem) # add the problem to the queue
def __lt__(self, other):
return self.__weight > other.__weight # note the >
def __repr__(self): # to show in lists
return "Problem({}, {})".format(self.__name, self.__weight)

等!为什么是"低于"和>?这是因为模块heapq是一个最小堆:它首先返回最小的元素。因此,我们将大权重定义为小于小权重。

现在,我们可以为示例构建一个包含假数据的开始队列:

queue = []
for name in ["foo", "bar", "baz"]:
problem = Problem(name, random.randint(0, 100))
heapq.heappush(queue, problem) # add the problem to the queue

并运行主循环:

while queue:
print ("Current queue", queue)
problem = heapq.heappop(queue) # the problem with the max weight in O(lg n)
problem.handle(queue)

我想您将能够对Problem类进行子类化,以表示您可能想要处理的各种问题。

最新更新