Replacing a vertical sublist in a list of lists

Question

This question is an extension to this question.

I'm representing a two-dimensional array using list of lists, L, say:

[ [1, 2, 3, 4],
  [1, 2, 3, 4],
  [1, 2, 3, 4],
  [1, 2, 3, 4] ]

For a given sub-list, say [9, 99], I want to replace a specific sub-list in the "2-D" list by this sublist using something intuitive like:

L[1][0:2] = sublist

# which updates `L` to:

[ [1, 2, 3, 4],
  [1, 9, 99, 4],
  [1, 2, 3, 4],
  [1, 2, 3, 4] ] # not in this format, but written like this for clarity

This works for horizontal replacements, but not for vertical replacements since, as we can't slice to separate lists like this: L[0:2][0]. If I had to use this slicing system, I could transpose L (Transpose list of lists), then use this slicing method, then transpose it back. But that's not efficient, even for the sake of simplicity.

What would be an efficient way to replicate L[0:2][0] and get this output?

[ [1, 2, 3, 4],
  [1, 9, 3, 4],
  [1, 99, 3, 4],
  [1, 2, 3, 4] ]

Note: Assume len(sublist) <= len(L), for vertical replacements (which is the focus of this question).

@Kasramvd I want a solution without Numpy if possible. All other standard functions are fine — Ajit Panigrahi, Feb 09 '18 at 18:07
How do you want to receive the parameters? Is sublist and index (in this case column) ok? — Walucas, Feb 09 '18 at 18:12
L[0:2][0]=L[0][0]+L[1][0], so treat vertical replacements as loop for horizontal replacements — Sphinx, Feb 09 '18 at 18:16
@Walucas Yes. I wanted a one-liner assignment like that of the example I gave for horizontal sub-list replacement, but anything is better if it's more performant. — Ajit Panigrahi, Feb 09 '18 at 18:28
@Sphinx I've tried that and, of course, it works. I wanted a more concise way to do it like that of the example I gave to horizontal sub-list replacement. — Ajit Panigrahi, Feb 09 '18 at 18:29
I don't think exists more efficient way. Because the data is saved in memory by horizontal not vertical. Anyway, the memory still can't support horizontal and vertical at the same time until now. — Sphinx, Feb 09 '18 at 18:38
u don't want to transpose at all? even without numpy, like list(zip(*l)) — Walucas, Feb 09 '18 at 18:46
@Walucas until now, we come out two solutions: 'transpose' or 'loop for horizontal replacement', which way is more efficient? — Sphinx, Feb 09 '18 at 19:01
Is `replaceVert(a,['ä','ü'],2,2)` a one liner? That would be the looped variant. I leave the zipped (==transpose/slice/transpose) version in, for ppl that find this question later on. — Patrick Artner, Feb 09 '18 at 19:06

Patrick Artner · Accepted Answer · 2018-02-09T19:34:47.137

Looping approach:

def replaceVert(al : list, repl:list, oIdx:int, iIdx:int):
    for pos in range(len(repl)):
        al[oIdx+pos][iIdx] =  repl[pos]

a = [ [1, 2, 3, 4],
      [5, 6, 7, 8],
      [9, 10, 11, 12],
      [13, 14, 15, 16] ]

print(a)   # [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

replaceVert(a,['ä','ü'],2,2)  # this is a one liner ;)

print(a)   # [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 'ä', 12], [13, 14, 'ü', 16]]

Transpose/slice/transpose approach:

I overread the mentioning of "no transposing". This is using transpose, change, transpose method with slicing which is not wanted by the Q. It is a answer for the title of this question, so I decided to leave it in for future people search SO and stumble over this Q:

a = [ [1, 2, 3, 4],
      [5, 6, 7, 8],
      [9, 10, 11, 12],
      [13, 14, 15, 16] ] 

b = list(map(list,zip(*a)))  # will make [ [1,5,9,13], ... ,[4,8,12,16]]
b[1][0:2]=['a','b']          # replaces what you want here (using a and b for clarity)
c = list(map(list,zip(*b)))  # inverts b back to a's form

print(a)
print(b)
print(c)

Output:

[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]     # a
[[1, 5, 9, 13], ['a', 'b', 10, 14], [3, 7, 11, 15], [4, 8, 12, 16]] # b replaced 
[[1, 'a', 3, 4], [5, 'b', 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] # c

Timing 4x4 list, 2 replaces:

setuptxt = """
def replaceVert(al : list, repl:list, oIdx:int, iIdx:int):
    for pos in range(len(repl)):
        al[oIdx+pos][iIdx] =  repl[pos]

a = [ [1, 2, 3, 4],
      [5, 6, 7, 8],
      [9, 10, 11, 12],
      [13, 14, 15, 16] ]
"""
zipp = """b = list(map(list,zip(*a)))  
b[1][0:2]=['a','b']           
c = list(map(list,zip(*b)))
"""

import timeit

print(timeit.timeit("replaceVert(a,['ä','ü'],2,2)",setup = setuptxt))
print(timeit.timeit(stmt=zipp, setup=setuptxt))

Output:

looping: 12.450226907037592
zipping: 7.50479947070815

The method wit ZIPPing (transpose/slice/transpose) needs roughly 60% of the time for 4x4 lists.

Bigger list 1000x1000 and ~70 elements replaced:

setuptxt = """
def replaceVert(al : list, repl:list, oIdx:int, iIdx:int):
    for pos in range(len(repl)):
        al[oIdx+pos][iIdx] =  repl[pos]

a = [ [kk for kk in range(1+pp,1000+pp)] for pp in range(1,1000)] 
repl = [chr(mm) for mm in range(32,100)]
"""

import timeit


print(timeit.timeit("replaceVert(a,repl,20,5)",number=500, setup = setuptxt))

zipp = """b = list(map(list,zip(*a)))  
b[20][5:5+len(repl)]=repl           
c = list(map(list,zip(*b)))
"""

print(timeit.timeit(stmt=zipp, setup=setuptxt,number=500))

Output:

looping: 0.07702917579216137
zipping: 69.4807168493871

Looping wins. Thanks @Sphinx for his comment

@Sphinx thanks for pointing it out. I leave the answer in, because someone finding this questions won't know from the questions title that this solution in this situation is off-limits. — Patrick Artner, Feb 09 '18 at 18:52
Can you please provide `timeit` results for both the approaches? It seems there may not be a performant "pythonic" way to solve this question, which was my intention. Numpy is clearly a better solution, but I can't use it on online judges/competitions, hence this question. — Ajit Panigrahi, Feb 09 '18 at 19:08
I think Numpy uses first approaches=[looped-one-liner apporoach] for vertical replacements. If the matrix is very huge, I don't think transpose can be completed quickly. — Sphinx, Feb 09 '18 at 19:19

Replacing a vertical sublist in a list of lists

1 Answers1