9

Which is better optimization?

  • A series of if/else statement which receives the 'string' returns the appropriate function for it. (Around 40-50 if/else statements).
  • A dictionary maintaining the key-value pair. key as strings, and values as the function objects, and one main function to search and return the function object.

The main function which actually returns the function object using above method would be called millions or billions of times, so need to do this intelligently. What could be the better way?

For e.g.

dict['str1'] = func1
dict['str2'] = func2
and so on..

def main_func(str):
    return dict[str]

Or

def main_func(str):
    if 'str1':
      return func1
    elif 'str2':
      return func2

Which would be better..? if we have 50-60 such strings, and this process needs to be billions of times.

Storing function object inside dictionary, in function itself:-

def func1():
   if dict.has_key('str1'):
        dict['str1'] = func1
   -- do something --

Which is better, this or the above one. This looks much cleaner.? But remember, these functions would be called many times so has_key function would also be called many times.

Thanks

4

7 回答 7

16

选择字典。

词典 ...

  • 是内置的
  • 是pythonic
  • 需要更少的样板代码
  • 与 if-else 线性 O(n) 复杂度相比，具有 O(1) 复杂度
  • 不犯过早悲观（我们没有足够的理由相信没有分析它是一种效率较低的方法）

我建议先使用字典编写解决方案，然后查看解决方案是否足够快以满足您的需求。如果是这样，太好了，你完成了。如果没有，请按另一种方式计时。

None考虑这样的解决方案（如果找不到字符串，它将返回）：

func_dict = {}
func_dict['str1'] = fun1
func_dict['str2'] = fun2
...
def function_lookup(func_string):
    return func_dict.get(func_string)

然后，在您的 main 中，只需编写function_lookup(whatever_string_variable)以尝试查找您的函数。这样可以避免每次function_lookup调用时都重建字典。

于 2012-07-12T05:07:25.123 回答
6

字典会更快：它大约是 O(1)，而 if 语句链是 O(n)。为了演示，这个脚本 ( make_test.py) 将输出一个运行一些性能测试的 python 脚本：

ifs = []
dict = []
for i in range(60):
    string = 'str%d' % i
    ifs.append('  %sif str == "%s": return %d' % ('el' if i else '', string, i))
    dict.append('"%s": %d' % (string, i))

print 'dict = {', ','.join(dict), '}'
print 'def with_dict(str):'
print '  return dict[str]'

print 'def with_if(str):'
print '\n'.join(ifs)

print '''
import timeit

def test_dict():
    for i in range(60):
        with_dict("str%d" % i)

def test_if():
    for i in range(60):
        with_if("str%d" %i)

print 'dict:', timeit.timeit(test_dict, number=10000)
print 'if:  ', timeit.timeit(test_if, number=10000)'''

运行它python make_test.py | python，给我：

dict: 0.706176042557
if:   1.67383503914

即if版本比dict版本慢2倍以上。

于 2012-07-12T05:13:16.753 回答
2

从技术上讲，它取决于哈希冲突性能，但我想将所有数据存储在哈希中并检索它会稍微快一些。

无论如何，无论哪种方式，差异都可能不会很大。当然，哈希表解决方案更干净，所以我会推荐它。

确定的最好方法是编写两个版本并用大量数据测试它们并测量它们的性能。

于 2012-07-12T05:01:08.390 回答
2

字典更好。字典应该由树/哈希图支持，并且比 if-else 语句（大致是线性的）具有更好的时间复杂度。即使实际运行时间不是更好，使用字典代码也会更干净。

于 2012-07-12T05:01:52.223 回答
2

字典是 python 中经过大量调整的部分之一。它们产生更具可读性的代码。它们应该比你的 if 循环表现更好。但是，考虑到插入和其他开销，我建议您使用 timeit 模块并检查性能。

于 2012-07-12T05:07:46.930 回答
0

dict 查找的平均时间复杂度为O(1)。最坏的情况是 O(n)。只有 str 键（您的用例）的字典有优化。

假设 if/else 阶梯中的测试顺序本身不能根据输入的频率进行优化（例如 60 种可能性，其中 2 种出现 95% 的时间），一系列 if/else 语句的复杂性是 O(n)。

因此，字典将提供更好的性能以及更好的代码可读性。

于 2012-07-12T05:14:41.543 回答
-1

每个解决方案看起来更优雅，更容易维护。

在大多数应用程序编程中，优化人工时间和可维护性比优化计算机时间更重要。电脑时间很便宜。人的时间是昂贵的。

两种解决方案都有其优势。

如果您需要稍后添加控制流，例如嵌套 if/else，if/elif 解决方案可能会提供更大的灵活性。

如果数据直接来自像 yaml 或数据库这样的数据源，那么显然 dict 解决方案更优雅。

于 2014-10-30T23:20:44.960 回答