Python mini-challenge: "Lucky" numbers

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 2860 Views - Last Post: 10 February 2014 - 07:13 AM Rate Topic: -----

#16 Mbare  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 02-September 12

Re: Python mini-challenge: "Lucky" numbers

Posted 10 February 2014 - 05:25 AM

HI good exercise for learn ;)/>
Mekire's solution seems pretty good but we can improve efficiency with list comp. and hash table.
And above all: Donít use *list + list* ! use *extend* instead or better *chain* from itertools

l = list(range(1, 100))
def process_list(_list):
        _list  = _list[::2]
        _index = 1
        while _index < len(_list):
            _step   = _list[_index]
            _avoid_indx = {(i - 1): None for i in range(0, len(_list), _step)}  # Hash table search items in O(1)
            _list   = [i for i in _list if _list.index(i) not in _avoid_indx]
            _index += 1
        return _list



now only for *didactics* purpose we know that Pythonís list class relies on an algorithmic sleight : dynamic array. very efficient but not for all.(not for real time process for example)
The first key to providing the semantics of a dynamic array is that a list instance
maintains an underlying array that frequently has greater capacity than the current length
of the list. --> Pythonís implementation of the append method shows amortized constant-time behavior (otherwise it would work in linear time)

finally parsing item's list works in O(n) linear time, instead hash table works in O(1).
Was This Post Helpful? 0
  • +
  • -

#17 Mekire  Icon User is offline

  • D.I.C Head

Reputation: 116
  • View blog
  • Posts: 212
  • Joined: 11-January 13

Re: Python mini-challenge: "Lucky" numbers

Posted 10 February 2014 - 06:09 AM

Quote

Mekire's solution seems pretty good but we can improve efficiency with list comp. and hash table.

No offense intended, but did you actually test this on a large set.
The time complexity of this is not lower than mine.

In fact this line alone is slowing you down dramatically:
_list   = [i for i in _list if _list.index(i) not in _avoid_indx]
As list.index is already a O(n) operation that comprehension alone is O(n^2).
This is a situation where enumerate does wonders as you already have the index at your disposal:
_list   = [i for index,i in enumerate(_list) if index not in _avoid_indx]
However this is still too slow.

Quote

Don’t use *list + list* ! use *extend*
On this point, I am aware of extend and find it makes no difference. Adding on to a list of length n is still O(k) regardless, where k is the length of the list you are adding (at least as far as I understand). The itertools.chain suggestion may help however; currently trying to apply it.

-Mek

This post has been edited by Mekire: 10 February 2014 - 06:11 AM

Was This Post Helpful? 0
  • +
  • -

#18 Mbare  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 02-September 12

Re: Python mini-challenge: "Lucky" numbers

Posted 10 February 2014 - 07:06 AM

HI

yes, I now noticed that you used += and not l + l then equivalent to extend ;)

right! of course my list comp. works at O(n^2) isnít a great improvement, but overall the func should have a *decent* efficency Ö however I have not tested it on large setÖ;) Iíll do that ;)

ps. In these cases probably the better solution would be a structure like a *doubly linked list* --> O(1)-time update operations, including insertions and deletions at arbitrary positions within the list, and of course to work with *numpy-array* but all this probably falls outside the purpose of this post
Was This Post Helpful? 0
  • +
  • -

#19 Mekire  Icon User is offline

  • D.I.C Head

Reputation: 116
  • View blog
  • Posts: 212
  • Joined: 11-January 13

Re: Python mini-challenge: "Lucky" numbers

Posted 10 February 2014 - 07:13 AM

View PostMbare, on 10 February 2014 - 02:06 PM, said:

[...]but all this probably falls outside the purpose of this post
Not at all, at least in my opinion. If you can come up with an implementation that uses either or both I would love to see it. I have hit a wall on optimizing mine and have instead been looking at overlaps in the prime/lucky sets. I did implement a version using itertools.chain to tie the lists together but ended up wasting more time than it saved.

-Mek
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2