2
\$\begingroup\$

This Python function takes two arguments:

  • chr_list which is a mutable sequence of characters c
  • chr_counts which maps to each character c the number of occurrences n

For each character c in chr_list, it inserts this character into the list before its last occurrence n-1 times, where n equals chr_counts[c]. The resulting list contains chr_counts[c] occurrences of each character c, and the order of last occurrences is preserved.

def insert_repetitions_before(chr_list, chr_counts):

  for c, num_occurences in chr_counts.items():
    num_repeats = num_occurences - 1
    orig_pos_last = chr_list.index(c)

    for curr_pos_last in range(orig_pos_last, orig_pos_last+num_repeats):
      random_pos_before_last = random.randint(0, curr_pos_last)
      chr_list.insert(random_pos_before_last, c)

Example output:

chr_list = ['c','o','d','e']
chr_counts = {'c': 3, 'o': 1, 'd': 2, 'e': 2}
>>> insert_repetitions_before(chr_list, chr_counts)
>>> chr_list
['c', 'd', 'c', 'c', 'e', 'o', 'd', 'e']

I want to make it more efficient. Currently its time complexity is O(n*m), n being the number of distinct characters and m the average number repetitions. Perhaps something like random.shuffle on a list containing all characters with repetitions, followed by some reordering?


(I'm not sure whether this is the right site to ask, since this question isn't quite specific to Python. Maybe I'll move it to CS.)

\$\endgroup\$
2
  • \$\begingroup\$ So chr_list contains exactly the keys of chr_counts exactly once each? \$\endgroup\$ Commented Mar 27, 2017 at 11:48
  • \$\begingroup\$ @PeterTaylor Yes, and each value in chr_counts is at least 1. \$\endgroup\$
    – kyrill
    Commented Mar 27, 2017 at 12:26

1 Answer 1

3
\$\begingroup\$

I want to make it more efficient. Currently its time complexity is O(n*m), n being the number of distinct characters and m the average number repetitions.

There are two important errors there. Firstly, the time complexity of the given code is worse than stated. Secondly, the stated complexity is optimal.

Taking those in reverse order: the stated complexity is optimal because the number of items which must be inserted into chr_list is \$\Theta(mn)\$, and no matter how you arrange things each insertion will take \$\Omega(1)\$ time.

However, the given code does insertions at random, and an insertion into a random position in a list takes \$\Theta(\textrm{len})\$ time, so the overall complexity of the given code should be \$\Theta(m^2 n^2)\$.


How to achieve optimal asymptotic performance? You need to arrange for the insertions to be done in order. I think that probably requires some additional datastructures. The simplest approach conceptually is to have an array (or a list in Python terms) to store the characters in their final positions and a datastructure of unassigned indexes which allows fast selection of the maximum element and a random element. In Pythonesque pseudocode:

tmpList = [None] * sum(chr_counts)
unassigned = new Datastructure(sum(chr_counts))
for c in reverse(chr_list):
  tmpList[unassigned.removeMax()] = c
  for i in 1 to chr_counts[c] - 1:
    tmpList[unassigned.removeRandom()] = c
copy tmpList to chr_list

The best implementation I've thought of so far for the datastructure of unassigned indexes combines a linked list for fast implementation of max with an array for fast implementation of random. I'm not familiar with Python's OO syntax, so this is again pseudocode:

class LinkedListNode:
  LinkedListNode prev
  LinkedListNode next
  int arrayIdx
  int value

class Datastructure:
  LinkedListNode[] array
  LinkedListNode sentinel = new LinkedListNode

  init(len):
    array = []
    for i in range(len):
      array[i] = new LinkedListNode { arrayIdx = i, value = i }
    for i in range(len-1):
      array[i].next = array[i+1]
      array[i+1].prev = array[i-1]
    sentinel.next = array[0]
    sentinel.prev = array[len-1]
    sentinel.next.prev = sentinel
    sentinel.prev.next = sentinel

  removeMax():
    return removeNode(sentinel.prev)

  removeRandom(rnd):
    randIdx = rnd.randint(0, len(array))
    return removeNode(array[randIdx])

  removeNode(node):
    # Remove from linked list
    node.next.prev = node.prev
    node.prev.next = node.next
    # Remove from array
    array[node.arrayIdx] = array[-1]
    array[node.arrayIdx].arrayIdx = node.arrayIdx
    del array[-1]

    return node.value

Note: I don't really think Datastructure is a good name, but it's not an easy class to name so I'm using it as a placeholder instead of Foo.

\$\endgroup\$
9
  • \$\begingroup\$ Correct me if I'm wrong, but max(unassigned) would be unnecessary if unassigned was ordered (ie. a list, not a set). Then you can just pick the last element. Also, unassigned.remove is linear-time operation with respect to size of unassigned. If you use a list, then it's just tmpList[unassigned.pop(-1)] = c. Either way, it's significantly faster than the original version. I might post a version with the efficient implementation of random you mentioned. \$\endgroup\$
    – kyrill
    Commented Mar 27, 2017 at 14:44
  • \$\begingroup\$ @kyrill, I don't think that either list or set have the desired performance, which is for max, random, and remove to all be constant time. That's why I suggested a composite data structure. To expand slightly, the linked list would be ordered (which is why max is fast) but the array would start ordered and become unordered (fast deletion by swapping the deleted element to the end). I also fudged the remove a bit: really max and random would have to return more complicated elements than just the index so that you can do that swap to the end without first searching for the node \$\endgroup\$ Commented Mar 27, 2017 at 14:49
  • \$\begingroup\$ I gave it some thought and it would be possible but ugly. You would need two arrays with three doubly-linked lists upon them to make it linear-time. One array will hold indices in order, a linked list will link these indices both ways to allow for quick deletions and max. Then a randomly shuffled array with indices and a linked list for this array (again quick deletions and random). Finally a linked list connecting these two arrays, to allow for quick deletions from max array when an index is picked from the random array and vice versa. There must be a nicer way to do it... \$\endgroup\$
    – kyrill
    Commented Mar 27, 2017 at 15:17
  • \$\begingroup\$ Actually the structure connecting the max and random arrays would not be a doubly-linked list but two maps (dictionaries). It would be nicer if implemented in OO-style, but arguably less efficient, especially since it's an interpreted language. \$\endgroup\$
    – kyrill
    Commented Mar 27, 2017 at 15:26
  • 1
    \$\begingroup\$ @kyrill, updated with more pseudocode. The reason for putting the node's info into the node itself rather than using a dictionary is that the node exists purely for the purposes of this datastructure, so we can do so without harming other code, and we save the overhead of a dictionary. \$\endgroup\$ Commented Mar 27, 2017 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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