0

How can I represent a list that contains only binary numbers (not integer) based on string list:

str_list = ['111111', '1111011', '11110011', '11111011', '111100011', '111110011']
bin_list = [111111, 1111011, 11110011, 11111011, 111100011, 111110011]

Starting from the point that the size of string and a bit are different, is that means search in the two list for the same element gave different time? Is the search method is the same for the both lists?

Bacara
  • 6,903
  • 1
  • 20
  • 21
  • 1
    The search method is the same, the `__eq__` method is different (and probably faster for integers). – Willem Van Onsem Feb 06 '17 at 12:24
  • I see integers, am I missing something? If you deal with floats you can convert the strings to floats and check the equivalence within the rounding error given by the accuracy you have from the strings. – terence hill Feb 06 '17 at 12:29
  • 2
    I agree with Willem. Apart from that, your `bin_list` doesn't contain binary numbers - it's just base-10 integers that only contain the digits 0 and 1. If you want to represent a binary number, use the prefix `0b` – Yotam Salmon Feb 06 '17 at 12:30
  • Whenever I use the 0b prefix, python threat bin_list element as string bin_list = [bin(0b111111), bin(0b1111011), bin(0b11110011), bin(0b11111011), bin(0b111100011), bin(0b111110011)] print type(bin_list[0]) – Bacara Feb 06 '17 at 12:48
  • 1
    You should **not** use `bin(..)` simply `bin_list = [0b11011,0b1101]`... The elements are the `int`s. – Willem Van Onsem Feb 06 '17 at 12:55

1 Answers1

1

The search method is defined on the list, and the only way to search in an unordered list is by iterating (of course the order in which to iterate is arbitrary, but there is no reason to use another one for another type of data, especially since you can put objects with different types in the same list).

So the list is basically unaware what elements are in it, and iterates over the list like:

# basic implementation of linear search
def __contains__(self, item):
    for elem in self:
        if item == elem:
            return True
    return False

Now the only thing that differs is the == method (and thus the underlying __eq__). Indeed: the equality of int's can be calculated more efficiently, since usually 32 or 64 bits can be compared at once (because that is how it is usually hardwired on a processor). This in contrast with strings, where one iterates over the the characters. So equality checks over ints are faster than the ones over strings.

Finally you can encode binary numbers more compact on an integer. For instance 1110 (binary) is equivalent to 14. You do not have to do the math yourself: as this answer says, you can simply write 0b1110 and Python will convert it to the int 14.

Community
  • 1
  • 1
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • In fact, I'm interested in complexity, and the search time where I have as mentioned str_list and bin_list, I think they are not the same since 0b010 != '010' (in size representation) – Bacara Feb 06 '17 at 12:58
  • Well as said before `0b010` is an **integer** (an `int` or `long`, etc). And here we can do comparisons 64 bits (or 32 bits at a time). If the integers are bounded (not always the case), then comparison is done in constant time. Otherwise they are both *O(n)* with *n* the length of the string/number. But since integers can compare a large amount of bits at a time, there is a huge speedup compared to strings anyway. – Willem Van Onsem Feb 06 '17 at 13:15