-3

Is it possible to get a slice of an array in constant time. if so what is the method .preferably in python .

ashes
  • 45
  • 6

2 Answers2

1

It is possible, and I don't know why people were saying differently. You just have to write your own class to do it and be careful with mutability. Basically you need to implement the same interface as a list, but be careful how you handle slices.

You could create a class called SliceList that is iterable and stores internally a list and two offsets into that list start and end. You would overload the [] operators so that x[i] really accessess x.internal_list[x.start + i]. You would also overload the __len__ to return end - start. The big issue would be you'd have a shallow copy of the internal data structure so modification of the original list would also modify any slices of the list. But this does make some algorithms, like a binary search algorithm, a lot cleaner to code, since the data structure would handle the internal index math and you would have to pass all of that explicitly.

Slicing then returns a new SliceList object with the same internal list, but a different start and end. Slices are now O(1).

John
  • 2,012
  • 2
  • 21
  • 33
0

Let the array be of size n. Constructing a slice that is a fraction of n takes O(n) time. In this related post the python notation is explained. You may also take a look at the python documentation on the time complexities. So the answer is no in general, only for a constant size slice it can be constant time.

gue
  • 1,868
  • 1
  • 16
  • 21
  • How does it answer OP question ? – Tony Tannous Jul 24 '17 at 22:13
  • @gue then is it possible to insert an element in constant time in any programming language because i have an algorithm that will sort in O(log(n!)) if it is possible either to slice or insert in constant time – ashes Jul 25 '17 at 06:24
  • Thank you for your help so far – ashes Jul 25 '17 at 06:24
  • The complexities are not dependent on the programming language. If we are speaking of an array we have a fixed size memory block that is addressed consecutively. Thus, inserting a new element always takes O(sizeof(array)) time as all elements behind have to be moved, or event the array resized. In a list this is of course no problem. – gue Jul 25 '17 at 08:01
  • but in a list accesing any ith element will take O(i) time. i cant have that i need O(1) time indexing any element and O(1) time for insertion for the sort to work in log(n!) – ashes Jul 25 '17 at 11:41
  • i guess its not possible Thank you for your help – ashes Jul 25 '17 at 11:42
  • So if your data structure has to be sorted (and presumably should stay sorted) you want most likely a priority queue. Searching in the sorted structure is O(log n) take a look at https://en.wikipedia.org/wiki/Priority_queue – gue Jul 25 '17 at 12:02
  • i dont think that will work too i briefly thought it was possible to beat nlogn – ashes Jul 25 '17 at 12:22
  • the algorithm was basically applying binary search to the sorted array formed during insertion sort to find the position where to insert the next element . assuming insertion of the element to the sorted part will be done in constant time t e runtime will be =log(1)+ log(2)..log(n)=log(n!) which would have been faster than nlogn – ashes Jul 25 '17 at 12:27