Reputation
336
Top tag
Next privilege 500 Rep.
Access review queues
Badges
1 5
Newest
 Critic
Impact
~15k people reached

  • 0 posts edited
  • 0 helpful flags
  • 33 votes cast
Apr
12
comment Why Variables in Python Are Different from Other Programming Languages?
"to C/C++, which use value types." C/C++ has value types and reference types. The "type" in Python is semantically equivalent to C/C++ pointers.
Mar
29
answered Bounded Type Parameters
Mar
29
comment Bounded Type Parameters
@lxrec: No, there is no "real type" in the body of the method. The called method does not know what U is.
Jan
27
comment Is garbage collection needed for implementing safe closures?
@JonHarrop: "RC is a form of GC." Under some definitions, yes. I should have said "tracing garbage collection", which is what people are talking about in this question.
Jan
27
comment Is garbage collection needed for implementing safe closures?
@JonHarrop: "SML is an impure language with full support for mutation." Did I every say that SML is a pure language or doesn't mutation? No. Read what I said.
Jan
27
comment Is garbage collection needed for implementing safe closures?
@JonHarrop: "Not it isn't. The value can contain a pointer." So? There are also pointer variables outside closures. A pointer variable captured by a closure is no less safe than a pointer variable outside a closure.
Jan
9
comment How are objects stored in unordered_sets?
C++ is just a specification. It specifies the requirements that library functions and types must have (including time complexity of operations). C++ library implementations (of which there are many) are free to implement it however they like as long as it satisfies the requirements in the language specification. The programmer generally shouldn't rely on any details of the implementation except those required by the language. If you are asking how a particular implementation implements it, or how you might implement it yourself, you should say so in your question.
Dec
5
comment In Java, should I use “final” for parameters and locals even when I don't have to?
"final doesn't guarantee that you can't change the value/state of a (nonprimitive) variable. Only that you can't reassign the reference to that object once initialized." Nonprimitive = reference (the only types in Java are primitive types and reference types). The value of a variable of reference type is a reference. Therefore, you can't reassign the reference = you can't change the value.
Aug
6
comment How can the containsKey() method of a Java Hash Table be O(1)?
In any case, both the "worst-case amortized complexity" and "worst-case non-amortized complexity" for lookup in this hash table is O(n), and both the "average-case amortized complexity" and "average-case non-amortized complexity" for lookup in this hash table is O(1), so the mention of "amortized" is pointless in any case. Amortization cannot affect the complexity of lookup because lookup is a non-mutating operation -- one lookup should not have any effect on the complexity of a future lookup -- so the cost redistribution of amortization cannot come into play.
Aug
6
comment How can the containsKey() method of a Java Hash Table be O(1)?
Amortization talks about a particulGranted, it is possible to talk about "average-case amortized complexity" and "worst-case amortized complexity", etc., but without explicit qualification "amortized complexity" generally means "worst-case amortized complexity".
Aug
6
comment How can the containsKey() method of a Java Hash Table be O(1)?
No matter what data structure you are looking at, amortization cannot affect the complexity of lookup because lookup is a non-mutating operation, so one lookup should not have any effect on the complexity of a future lookup. Therefore, the fact that you have different complexities for amortized and non-amortized for the same case indicates that something is definitely wrong.
Aug
6
comment How can the containsKey() method of a Java Hash Table be O(1)?
@Jules: And about hash table lookup being amortized O(1), the article first assumes that you have a good hash function and the operations are O(1), and then does an amortized analysis of the cost of adding an element considering resizing. It is NOT saying that in the worst case the amortized cost is O(1). In the worst case it is amortized O(n).
Aug
6
comment How can the containsKey() method of a Java Hash Table be O(1)?
@Jules: I said "CS source" with respect to the definition of "amortized", which the source clearly says means average of a sequence of operations on the same data structure, for a particular set of inputs. You cannot average over different inputs.
Aug
5
comment How can the containsKey() method of a Java Hash Table be O(1)?
@Jules: Yes, what I said is exactly what "amortized" means. Read any CS source and it will say exactly that. Just because somebody edited the Wikipedia article to make it wrong does not change what it means.
Aug
5
comment How can the containsKey() method of a Java Hash Table be O(1)?
@gnat: No. You said "and properly implemented hash tables maintain it so that it remains O(1)", which makes it sound like the hash table can be "implemented" in some smart way so that it's always O(1). But that's wrong.
Aug
5
comment How can the containsKey() method of a Java Hash Table be O(1)?
so you agree that in the worst case, it is O(n)?
Aug
5
comment How can the containsKey() method of a Java Hash Table be O(1)?
"@JacquesB explains how this amortization works for hash tables." No he doesn't.
Aug
5
comment How can the containsKey() method of a Java Hash Table be O(1)?
"amortized worst-case step complexity of O(1)" No. The amortized worst-case step complexity for lookup for hashed data structures in Java is O(n).
Aug
5
comment How can the containsKey() method of a Java Hash Table be O(1)?
@gnat: It is impossible for it to be O(1) in the worst case
Aug
5
comment How can the containsKey() method of a Java Hash Table be O(1)?
@gnat: "and properly implemented hash tables maintain it so that it remains O(1)" There is nothing that a general Map can do to avoid collisions. Hash codes are provided by the objects themselves, and there can always be collisions due to 1) the class implementing hashCode that way, or 2) even if the class implements it well, elements can be chosen with the same hash code.