3
\$\begingroup\$

About to get back into coding, so I implemented linear probing in Python. How did I do? Anything unnecessary? Am I using "global" right? I originally wanted to use an array with a fixed length, but couldn't get it to work.

list = ["x", "x", "x", "x", "x", "x", "x"]
state = 0

def main():
#tests
    linearProbing(1)
    linearProbing(1)
    linearProbing(1)
    print(list)

def linearProbing(x):
    global state
    global list
    c = x % len(list)
    while state != 1:
        if list[c] == "x":
            list[c] = x
            state = 1
        elif c == 0:
            c = len(list) - 1
        else:
            c -= 1
    state = 0

if __name__ == '__main__':
    main()
\$\endgroup\$
3
\$\begingroup\$

Am I using "global" right?

It would be better to not use global at all, by wrapping this in a class, with state and list as attributes, so an instance could reference them with self.state, for example.

How did I do?

state is used as a boolean. So it should be a boolean value, set to False instead of 0 and True instead of 1 values.

list is not a good name for a variable, as it shadows a built-in with the same name.

A quick tip: you can write ["x", "x", "x", "x", "x", "x", "x"] simpler as ["x"] * 7. In any case, duplicating "x" in multiple places (first when you initialize list, and then later in linearProbing), is not great. It would be better to put the value "x" in a variable, say FREESPOT = "x", and reuse that everywhere.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's the kind of answer I was looking for, thank you very much :) \$\endgroup\$ – user74367 May 25 '15 at 19:11
1
\$\begingroup\$

Global variables

list should not be global, because it limits your function to ever working on one global list, hindering code reuse. Instead, it should be passed as a parameter. Since list is the name of a built-in type in Python, you should probably avoid using it as the name of a variable — that would break code like list(range(7)).

state should absolutely not be global. It's just a flag that is used locally within the linearProbing() function, and it's always 0 whenever linearProbing() is not executing. Better yet, just don't use flag variables for controlling program flow (see solution below).

Especially if you are a beginner, you should just consider global to be taboo, and avoid using it altogether. There is always a better way.

Other issues

  • There is no way to tell when the list is full (at which point the insertion silently fails, leading to probable data loss).
  • Using "x" as a special value to indicate an available slot is weird. Typically, None would be used for that purpose.
  • Counting loops are typically written using for … in range(…).
  • You can take advantage of the fact that negative list indices refer to positions relative to the end of the list.
  • Write a docstring. It's a good habit.

Suggested solution

def linear_probe(x, lst):
    """
    Put integer x into a list at position x % len(lst), probing
    backwards until a free spot is found.  Raise IndexError if
    the list is full.
    """
    preferred_index = x % len(lst)
    for c in range(preferred_index, preferred_index - len(lst), -1):
        if lst[c] is None:
            lst[c] = x
            return
    raise IndexError('list is full')

def main():
    # Tests
    lst = [None] * 7
    linear_probe(1, lst)
    linear_probe(1, lst)
    linear_probe(1, lst)

if __name__ == '__main__':
    main()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.