is deeper then i expected.
What is the running time of conactination on character strings.
i.e.
joe="123"
joe+="99999999999999999"
is it Amortized Constant time? I don't think it would be O((number of
chars)^2) but i really don't know.
Teach me how to fish, where would i find out more about the
internal
representations of data types in python (and guarenteed run times, im
think of something like sgi.com 's info on the STL) . I have looked
through the docs but i don't seem to see these types of specifications.
thanks * 100
- Haz
P.S.
- Should Note that i am famliure with timeit, but understanding the
underly data structures and representations is an important thing to
know.
P.P.S
This a bit of what i think relevent discourse i have been having via a
email responder of my usenet posting.
Haz> i should have mentioned that i am familure with the timeit
Haz> function, but shurly there must be a specification in the language
Haz> of the running time (number of flops).
Nope. I can't think of an instance where it would be appropriate to specify
runtime properties of various algorithms in the language. For example, if
you were to specify that sorting of lists was O(n log n) that would
potentially preclude the choice of quicksort as an algorithm because its
worst case behavior is O(n * n) even though it is generally faster than most
other sorting algorithms.
The answere here is to use omega(n log n) or specify average and worst
cases. I truely do think that there can be a complexity specification
for the language. I mean all algorithms have a complexity and surely
data structures are choosen with the size/speed tradeoffs in mind.
For instance in the STL has a sorting algorithm and it specifies a
running time the latter way (why they can do assure this is by using
coding with concepts, but i think in the base language it could be
simpler because the data structures are known.) i.e. Its know what
data types += works on and thus it should be know what algoritms are
to be used (that is the highly optimal ones)
From SGI STL Page: sort
<snip>
Complexity
O(N log(N)) comparisons (both average and worst-case), where N is last
- first. [2]
<snip>
source : http://www.sgi.com/tech/stl/sort.html
Haz> Without knowing these specifications its hard to optimize.
No, you still need to see where your program runs slow and figure out ways
to make it run faster.
Well basically my point is that it is hard to know why a code section
is running slow unless you understand the underlying data
represenations and algorithms
For instance
matlab code:
A=[]
for i=1:N
A=[A;'a']
end
is O(N^2) operation
C code:
vector<char> A;
for(i=0; i<N; i++){
A.push_back('a');
}
is Amortized O(N) [note that this isn't the correct wording exactly,
but in general is O(N)]
Python Code:
A=""
for i in range(N):
A+='a'
running time : ???
So if you are looking through your code in matlab or C and see this
concatination loop you know that it is a problem in the former and not
in the latter. But in python ???