>>1
O(n) to calculate the length of the string? Sure. What does that n mean in that case? How is it different from O(n) time to insert into the middle of an array?
Name:
Anonymous2012-02-12 3:27
>>1
Content-addressable memory could search, insert, or delete key-value pairs in O(1) time.
Name:
Anonymous2012-02-12 5:13
You can do it in O(1) under certain circumstances at compile time:
>>1
The n in the string hash is different from the n in the collection.
Name:
Anonymous2012-03-17 19:18
It's easy on a Turing machine, just use the infinitely long strings as indices into the infinite memory and keep the entries infinitely apart so any string can be stored.
That's possible, but it takes a bit more work. You could use the bijection between the set of all natural numbers and the set of all pairs of natural numbers to establish an infinitely long and wide two dimensional tape. Then you enumerate the set of all strings that could be inserted into the hash table, and store the ith string in the addresses (0, i) through (r, i), if the string has length r.
Name:
142012-03-17 22:35
and the address translation from the 2D tape to the 1D tape would need to be performed in order one time.
>>17
righto, a subset can be represented as a function from the super set domain to true or false, where the function is true for members of the set and false for members of the super set that are not in the set being represented by the function. If the elements of the super set can be enumerated, then the function can be represented on a tape as an array of bits, where the ith bit is on if and only the ith element of the super set is in the represented set. In this case, the super set is the set of all strings, which happens to be countably infinite. So as long as the has at least countably infinite slots, we are good for storing the table. Although one would need to index into the look up table fast enough to satisfy the order one look up. It shouldn't take any time longer than the length of the string being queried. Whether or not that can be done kind of depends on what assumptions you can make about the machine.
*So as long as the tape has at least countably infinite slots,
Name:
kaoli@sipb.mit.edu2012-03-18 10:19
>>18
>a subset can be represented as a function from the super set domain to true or false, where the function is true for members of the set and false for members of the super set that are not in the set being represented by the function.
That's not a function.
Name:
Anonymous2012-03-18 10:36
It's possible if you used the address of the string. You would need to intern all the strings obviously.
>>22
Here's a non trivial example. Consider 'boolean' operations in C. I can think of a few cases where the set same of integers would map to *both* 'true' and 'false'. In such a case, this wouldn't be a function. Now shut your hole you non programming bitch.
Name:
Anonymous2012-03-18 13:18
>>24
I can think of a few cases where your wrong britches.
Name:
Anonymous2012-03-18 13:28
>>25
The point is that your statements don't apply in general. And if you think they do, then like, you really are a fucking retard. Man, go back to /g.
Name:
Anonymous2012-03-18 13:34
>>23
Yes it is, it's a function whose domain is the super set and it maps to {true, false}. This is math 101, go back to school you stupid piece of shit.
Name:
Anonymous2012-03-18 13:37
>>24
You seem awfully confused, there is no ambiguity here. Sets are unordered so the situation will never occur.
{1,2,3} is the same as {2,3,1}, and {2,3,1} is either a member of the set were talking about or not, so it's either true or false, never both.
Name:
Anonymous2012-03-18 13:37
>>27
In C, it's possible to have boolean mappings that aren't one to one, and hence, not a function. Man, learn how languages like C work you no talent programming bitch.
Name:
Anonymous2012-03-18 13:39
>>28
In some languages, there are cases where they can be both you dumbass.
Name:
Anonymous2012-03-18 13:39
>>29
C has nothing to do with the function defined you fucking retard, if that is how "boolean mappings" work in C then they're not a function, however the mathematical entity that was defined is a function.
Stop confusing yourself you stupid piece of shit.
Name:
Anonymous2012-03-18 13:40
>>30
Programming languages have nothing to do with this, it's talking about a mathematical entity.
How dumb can you fucking get? Revisit basic education you stupid piece of shit.
Name:
Anonymous2012-03-18 13:42
Besides it's just a simple selector function, should've been covered in the most elementary math course. You should try revisiting basic definitions like function, set, super set and subset.
Name:
Anonymous2012-03-18 13:42
>>32
Well, this is a programming board. And you still have no clue what you are talking about. Go scrub another toilet you no talent bitch.
Name:
Anonymous2012-03-18 13:44
>>34
You have no fucking clue what you're talking about, do you still not know what a fucking subset is? You're just as confused as the last time you tried to run your mouth, you don't know mathematics and that means that you will forever be a substandard programmer.
You're a fucking retard, if you weren't you would have no issue with mathematics.
Name:
Anonymous2012-03-18 13:45
>>32
Well, your lame attempt at a mathematical entity would break down in languages like C.
Name:
Anonymous2012-03-18 13:46
>>34,36
Keep backpedaling you fucking retard, it's always fun to destroy your sorry ass.
Name:
Anonymous2012-03-18 13:47
>>35
It won't even work over a subset you idiot. Have you ever written an actual line of code in your entire life? I bet you don't even work as a computer programmer.
Name:
Anonymous2012-03-18 13:47
>>38
Yes it will you stupid piece of shit, you don't even know what a subset is.
Does "every subset of a countable set is also countable" ring a bell?
Name:
Anonymous2012-03-18 13:48
>>37
I ain't backpeddling. What I'm saying is that your math model won't work for languages like C. And the fact that you can see this makes you a retard.