Python Data Structures - C1 Search

Python数据结构篇(1) 搜索

参考内容: 1.Problem Solving with Python Chapter5: Search and Sorting online_link 2.算法导论

搜索(或查找)总结

(1)顺序查找:O(n) (2)二分查找:O(lgn) (3)Hash查找:O(1)

概念:hash,hash table,hash function 哈希表_on_wiki

常用的哈希函数:

1.reminder method:取余数(size=11,下图对11取余数,例如17取余数得到6)

2.folding method: 分组求和再取余数

3.mid-square method:平方值的中间两位数取余数

4.对于由字符的元素可以尝试使用ord函数来将字符串转换成一个有序的数值序列。在Python中ord函数可以得到对应字符的ASCII码值。将所有字符的码值累加再取余数。

但是,对于通过回文构词法构成的字符串它们得到的值总是一样,为了解决这个问题,可以根据字符的位置添加一个权重。

From wiki

使用哈希查找,难免遇到冲突,该如何解决冲突(Collision Resolution)呢?

常用的解决冲突的办法:

1.open address(开放寻址):线性探测(linear probing)下一个位置,缺点是容易造成聚集现象(cluster),解决聚集现象的办法是跳跃式地查找下一个空槽。数值的顺序:(54, 26, 93, 17, 77, 31, 44, 55, 20).

2.quadratic probing(平方探测):一开始的hash值为h,如果不是空槽,那就尝试h+1,还不是空槽就尝试h+4,依次继续尝试h+9,h+16等等。

3.chain:利用链表链接起来

From wiki

分析hash查找的性能:一般使用平均查找长度来衡量,和装载因子有关

散列表的载荷因子定义为:$\alpha$ = 填入表中的元素个数 / 散列表的长度 $\alpha$是散列表装满程度的标志因子。由于表长是定值,$\alpha$与“填入表中的元素个数”成正比,所以,$\alpha$越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之,$\alpha$越小,标明填入表中的元素越少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是载荷因子$\alpha$的函数,只是不同处理冲突的方法有不同的函数。 对于开放定址法,荷载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了荷载因子为0.75,超过此值将resize散列表。

From wiki

下面的代码包含了顺序查找,二分查找,哈希查找(size=11, plus 1, reminder method)

def sequential_search(a_list, item):
    pos = 0
    found = False
    while pos < len(a_list) and not found:
        if a_list[pos] == item:
            found = True
        else:
            pos = pos+1
    return found

test_list = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequential_search(test_list, 3))
print(sequential_search(test_list, 13))


def binary_search(a_list, item):
    first = 0
    last = len(a_list) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if a_list[midpoint] == item:
            found = True
        else:
            if item < a_list[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(test_list, 3))
print(binary_search(test_list, 13))

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    #put data in slot
    def put_data_in_slot(self,key,data,slot):
        if self.slots[slot] == None: # '==None' ? or  'is None' ?
            self.slots[slot] = key
            self.data[slot] = data
            return True
        else:
            if self.slots[slot] == key: # not None
                self.data[slot] = data #replace
                return True
            else:
                return False

    def put(self, key, data):
        slot = self.hash_function(key, self.size);
        result = self.put_data_in_slot(key,data,slot);
        while not result:
            slot = self.rehash(slot, self.size);
            result=self.put_data_in_slot(key,data,slot);

    #reminder method
    def hash_function(self, key, size):
        return key % size

    #plus 1
    def rehash(self, old_hash, size):
        return (old_hash + 1) % size

    def get(self, key):
        start_slot = self.hash_function(key, len(self.slots))
        data = None
        stop = False
        found = False
        position = start_slot
        while self.slots[position] != None and not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position=self.rehash(position, len(self.slots))
                if position == start_slot:
                    stop = True
        return data

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, data):
        self.put(key, data)


if __name__ == '__main__':
    table=HashTable();
    table[54]='cat';
    table[26]='dog';
    table[93]='lion';
    table[17]="tiger";
    table[77]="bird";
    table[44]="goat";
    table[55]="pig";
    table[20]="chicken";
    print table.slots;
    print table.data;

# [77, 44, 55, None, 26, 93, 17, None, None, 20, 54]
# ['bird', 'goat', 'pig', None, 'dog', 'lion', 'tiger', None, None, 'chicken', 'cat']

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

3. 统计数字暴力破解找规律

计算数字k在0到n中的出现的次数,k可能是0~9的一个值 样例: 例如n=12,k=1,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1...

2563
来自专栏游戏开发那些事

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

1164
来自专栏飞雪无情的博客

Go语言性能优化-两数之和算法性能研究

好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,...

1903
来自专栏和蔼的张星的图像处理专栏

162. 矩阵归零先找为零的位置,再分别置零

给定一个m×n矩阵,如果一个元素是0,则将其所在行和列全部元素变成0。 需要在原矩阵上完成操作。

1451
来自专栏猿人谷

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

2608
来自专栏ThoughtWorks

TW洞见 | 崔鹏飞:Scala中Stream的应用场景及其实现原理

假设一个场景 需要在50个随机数中找到前两个可以被3整除的数字。 听起来很简单,我们可以这样来写: ? 一个产生50个随机数的函数; 一个检查某数字是否能被3...

3394
来自专栏专知

Numpy教程第2部分 - 数据分析的重要功能

【导读】Numpy是python数据分析和科学计算的核心软件包。 上次介绍了numpy的一些基础操作。例如如何创建一个array,如何提取array元素,重塑(...

4459
来自专栏偏前端工程师的驿站

JS魔法堂:彻底理解0.1 + 0.2 === 0.30000000000000004的背后

Brief                                 一天有个朋友问我“JS中计算0.7 * 180怎么会等于125.9999999999...

3046
来自专栏趣谈编程

外部排序

当我们要排序的文件太大以至于内存无法一次性装下的时候,这时候我们可以使用外部排序,将数据在外部存储器和内存之间来回交换,以达到排序的目的

1600
来自专栏数据结构与算法

2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

3144

扫码关注云+社区

领取腾讯云代金券