0

When I try to make and hash objects from a file, containing one million songs, I get a weird segmentation error after about 12000 succesfull hashes.

Anyone have any idea why this:

Segmentation fault: 11

happens when I run the program?

I have these classes for hashing the objects:

class Node():
    def __init__(self, key, value = None):
        self.key = key
        self.value = value

    def __str__(self):
        return str(self.key) + " : " + str(self.value)

class Hashtable():
    def __init__(self, hashsize, hashlist = [None]):
        self.hashsize = hashsize*2
        self.hashlist = hashlist*(self.hashsize)

    def __str__(self):
        return self.hashlist

    def hash_num(self, name):
        result = 0
        name_list = list(name)
        for letter in name_list:
            result = (result*self.hashsize + ord(letter))%self.hashsize
        return result

    def check(self, num):
        if self.hashlist[num] != None:
            num = (num + 11**2)%self.hashsize#Kolla här jättemycket!
            chk_num = self.check(num)#här med
            return chk_num#lär dig
        else:
            return num

    def check_atom(self, num, name):
        if self.hashlist[num].key == name:
            return num
        else:
            num = (num + 11**2)%self.hashsize
            chk_num = self.check_atom(num, name)#läs här
            return chk_num#läs det här

    def put(self, name, new_atom):
        node = Node(name)
        node.value = new_atom
        num = self.hash_num(name)
        chk_num = self.check(num)
        print(chk_num)
        self.hashlist[chk_num] = node

    def get(self, name):
        num = self.hash_num(name)
        chk_num = self.check_atom(num, name)
        atom = self.hashlist[chk_num]
        return atom.value

And I call upon the function in this code:

from time import *
from hashlist import *
import sys

sys.setrecursionlimit(1000000000)

def lasfil(filnamn, h):
    with open(filnamn, "r", encoding="utf-8") as fil:
        for rad in fil:
            data = rad.split("<SEP>")
            artist = data[2].strip()
            song = data[3].strip()
            h.put(artist, song)

def hitta(artist, h):
    try:
        start = time()
        print(h.get(artist))
        stop = time()
        tidhash = stop - start
        return tidhash
    except AttributeError:
        pass

h = Hashtable(1000000)
lasfil("write.txt", h)
4

1 に答える 1

4

セグメンテーション違反が発生する理由は、次の行です。

sys.setrecursionlimit(1000000000)

を受け取ったので追加したと思いますRuntimeError: maximum recursion depth exceeded。再帰制限を引き上げても、呼び出しスタックにメモリが割り当てられることはなく、前述の例外が延期されるだけです。設定値が高すぎると、インタープリターがスタック スペースを使い果たし、スタック スペースに属さないメモリーにアクセスし、ランダム エラーが発生します (セグメンテーション違反の可能性がありますが、理論上は何でも可能です)。

本当の解決策は、無制限の再帰を使用しないことです。再帰の深さが数十レベルに制限されているバランスのとれた探索木の​​ようなものでは問題ありませんが、長いループを再帰に置き換えることはできません。

また、これがハッシュ テーブルを作成する演習でない限り、組み込みのdict. ハッシュ テーブルを作成する演習である場合は、これをハッシュ テーブルに関する何かがおかしいというヒントと考えてください。これは、プローブの長さが少なくとも 1000、おそらく数千であることを示しています。せいぜい数十、理想的には 1 桁である必要があります。

于 2013-10-11T14:52:49.007 に答える