<commit_before>---
layout: post
title:  "python搜索效率研究"
author: <NAME>
date:   2017-06-04 21:22:37 +0800
categories: 嵌入式开发
tags: python
excerpt: 分析python在字典和列表中的搜索效率
---

* menu
{:toc}

> 天地不仁，以万物为刍狗 --老子

本文来研究在python中查找元素的效率问题，实验方法如下：

1. 初始化一个大列表和字典，其中分别存放了10000000个元素。
2. 查找的元素以1000000的间隔递增，检测程序执行速度。
3. 自己实现顺序比较查找，用同样的方法进行测试，并和其他方法进行对比。

## 一、程序实现

程序实现包含上述三个查找算法，均很简单。

### 1.1 通过item in list实现查找

```
def find_item_in_list(item, mylist):
    if item in mylist:
        return True
    else:
        return False
```

### 1.2 通过dict.has_key实现查找

```
def find_item_in_dict(item, mydict):
    return mydict.has_key(item)
```

### 1.3 自定义顺序遍历查找

```
def my_find_in_list(item, mylist):
    for each in mylist:
        if item == each:
            return True
    return False
```

### 1.4 测试接口及shell脚本

driver如下

```
if __name__ == "__main__":
    # contribute list and dict
    len = 10000000
    mylist = []
    mydict = {}
    for i in range(len):
        mylist.append(i)
        mydict[i] = True

    start = time.clock()
    num = int(sys.argv[1])
    #find_item_in_dict(num, mydict)
    #find_item_in_list(num, mylist)
    my_find_in_list(num, mylist)<commit_msg>update article: python搜索效率研究<commit_after>---
layout: post
title:  "python搜索效率研究"
author: <NAME>
date:   2017-06-04 21:22:37 +0800
categories: 嵌入式开发
tags: python
excerpt: 分析python在字典和列表中的搜索效率
---

* menu
{:toc}

> 天地不仁，以万物为刍狗 --老子

本文来研究在python中查找元素的效率问题，实验方法如下：

1. 初始化一个大列表和字典，其中分别存放了10000000个元素。
2. 查找的元素以1000000的间隔递增，检测程序执行速度。
3. 自己实现顺序比较查找，用同样的方法进行测试，并和其他方法进行对比。

## 一、程序实现

程序实现包含上述三个查找算法，均很简单。

### 1.1 通过item in list实现查找

```
def find_item_in_list(item, mylist):
    if item in mylist:
        return True
    else:
        return False
```

### 1.2 通过dict.has_key实现查找

```
def find_item_in_dict(item, mydict):
    return mydict.has_key(item)
```

### 1.3 自定义顺序遍历查找

```
def my_find_in_list(item, mylist):
    for each in mylist:
        if item == each:
            return True
    return False
```

### 1.4 测试接口及shell脚本

driver如下

```
if __name__ == "__main__":
    # construct list and dict
    len = 10000000
    mylist = []
    mydict = {}
    for i in range(len):
        mylist.append(i)
        mydict[i] = True

    start = time.clock()
    num = int(sys.argv[1])
    #find_item_in_dict(num, mydict)
    #find_item_in_list(num, mylist)
    my_find_in_list(num, mylist)
{'fraction_non_alphanumeric': 0.12945670628183362, 'fraction_numerical': 0.04499151103565365, 'mean_word_length': 3.216457960644007, 'pattern_counts': {'":': 2, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7657036', 'n_tokens_mistral': 1264, 'n_tokens_neox': 1297, 'n_words': 201}