CODEWITHSUNDEEP
pythonperformancedata-structures
Dusan Krantic
Dusan Krantic

Reputation: 117

python fastest 'structure' access implementation

I have a data structure which consists of a fixed number of fields and a recursive function which does some processing on a list of these structures. In each iteration, the function accesses some particular list element (data structure), analyzes all its fields and (based on the field values) modifies the list by removing or adding new data structure elements.

I was wondering what would be the most efficient way to implement this data structure? I guess that the most sensitive aspects are the creation of a new structure and accessing the structure fields. I did some testing on structures with 10 fields:

  1. Implement as a list:
print("List")

def list_f ():
  l = [1,2,3,4,5,6,7,8,9,10]
  a1 = l[0]
  a2 = l[1]
  a3 = l[2]
  a4 = l[3]
  a5 = l[4]
  a6 = l[5]
  a7 = l[6]
  a8 = l[7]
  a9 = l[8]
  a10 = l[9]

print(timeit("list_f()", "from __main__ import list_f"))

Output:

List
0.4056466743350029
  1. Implement as a dict:
print("Dict")

def dict_f ():
  d = {"1":1, "2":2, "3":3, "4":4, "5":5, "6":6, "7":7, "8":8, "9":9, "10":10}
  a1 = d["1"]
  a2 = d["2"]
  a3 = d["3"]
  a4 = d["4"]
  a5 = d["5"]
  a6 = d["6"]
  a7 = d["7"]
  a8 = d["8"]
  a9 = d["9"]
  a10 = d["10"]

print(timeit("dict_f()", "from __main__ import dict_f"))

Output:

Dict
0.6061008963733912
  1. Implement as a class:
print("Class")

class C (object):
  
  def __init__(self, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10):
    self.a1 = a1
    self.a2 = a2
    self.a3 = a3
    self.a4 = a4
    self.a5 = a5
    self.a6 = a6
    self.a7 = a7
    self.a8 = a8
    self.a9 = a9
    self.a10 = a10

def class_f ():
  c = C(1,2,3,4,5,6,7,8,9,10)
  a1 = c.a1
  a2 = c.a2
  a3 = c.a3
  a4 = c.a4
  a5 = c.a5
  a6 = c.a6
  a7 = c.a7
  a8 = c.a8
  a9 = c.a9
  a10 = c.a10

print(timeit("class_f()", "from __main__ import class_f, C"))

Output:

Class
1.2926895800046623

It looks to me like lists are the most efficient solution. Do you know of any other implementation I could try, or how these execution times could depend on the number and type of structure fields?

EDIT:

Just as a clarification, the fields do not have the same type (I just used all int-s in the example), there will be some strings, some object handles and so on... I will never have to modify the fields on-the-fly. I know what values I want them to have when I create the structure, so I will initialize them and insert the structure into a list. The function only reads these values and removes the entire structure from the list upon finishing (and optionally creates completely new structure and inserts it into the input list). I am the one who defines both the structure and the function so I can adapt the function to efficiently work with any implementation.

Upvotes: 1

Views: 1123

Answers (4)

Dusan Krantic
Dusan Krantic

Reputation: 117

After some additional testing, I found that, as @{bruno desthuilliers} suggested, tuple provides the shortest access time so implemented it that way.

Upvotes: 0

anon
anon

Reputation:

Lists are editable objects, tuples aren't, dictionary is a unordered key-based data structure instead of an index-based as lists and tuples. Talking about performances, tuple and lists are slightly faster than dictionary but readability counts. So if that values have a meaning (maybe a1 is height of something, a2 is width, a3 is number of snakes in the room and so on) you should consider to use a dictionary. If they are the prices of BTC of the last 10 hours (one meaning for all the values) you could use a list. Tuple are not much used.

Upvotes: 0

GalacticDessert
GalacticDessert

Reputation: 36

Lists are effective in case you already know in advance the position of the desired element. Dictionaries have an advantage in case you have a key and you want to access a value, which can be done in constant time. A list access is also a linear time operation, but a lookup in case of unknown position is not, as it would require going though the elements until the right one is found.

Based on your description, I would say that dictionaries would be the most clear (as in code clarity) structure.

Upvotes: 1

dzang
dzang

Reputation: 2260

The answer to your question depends on what operations you need to perform and what data types you are going to store in your container. For the example you give a list is what makes most sense.

Assuming your point is speeding up your code, your alternative would be using vectorization. For example, if you are going to perform the same operation on each element, and you elements are numbers, then you could use a numpy.ndarray which would use a vectorized approach to perform the operation elemet wise. Avoiding a normal python loop would cut down execution time significantly.

Upvotes: 0

Related Questions