>>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.
Name:
Anonymous2012-03-18 13:50
>>39
In languages like C, it won't even work for a subset because the mappings aren't one to one.
Name:
Anonymous2012-03-18 13:50
>>40
You said that it wasn't a function, I pointed out that it obviously was. Now you're backpedaling saying that "it won't work in C", which wasn't even the fucking question in the first place.
Name:
Anonymous2012-03-18 13:51
>>42
It's not a function because the mappings aren't always one to one.
Name:
Anonymous2012-03-18 13:51
>>41
C doesn't change the definition of a subset you stupid piece of shit.
How many times do we have to go through this shit? Are you still trying to deny simple mathematical truth?
How can anyone this dumb even figure out how to post on the internet? It's like you failed every math course and had to take substandard programming courses instead.
Name:
Anonymous2012-03-18 13:53
>>42
It would only work if the mappings are one to one. However, for like the 8th time, the mappings aren't always one to one. The fact that you think they are just indicates to me that you've never actually written any kind of code in your entire life.
Name:
Anonymous2012-03-18 13:53
>>43
Jesus Christ you stupid piece of shit, look at the definition f(x) = 1, f is a function and it's not one to one.
You somehow confuse "function" with "injective function", no surprise there though, you're stupid as shit.
Name:
Anonymous2012-03-18 13:54
>>45
My god you fucking moron can't you read? It's not an injective function in your case but it's still a function.
You don't even know what a function is? You're so fucking retarded I can't believe it, how do you even figure out how to breathe?
Name:
Anonymous2012-03-18 13:55
>>44
You're right, C doesn't change the defintion of a subset. However, C's handling of booleans doesn impact the math defintion of a function.
Name:
Anonymous2012-03-18 13:56
>>48
Is that supposed to be does or doesn't? I'm amazed your stupid ass even managed to form something that looks a little bit like a sentence.
Name:
Anonymous2012-03-18 13:56
>>47
No, I can think of programming cases where it won't even be an injective function.
Name:
Anonymous2012-03-18 13:58
>>50
Can't you read you stupid piece of shit? I said it isn't an injective function, but it's still a function.
Now fuck off and revisit some basic mathematics.
Name:
Anonymous2012-03-18 13:59
>>51
Either way, I can think of like 3 cases where it's not a function. Learn more about structured programming you zero talent bitch.
Name:
Anonymous2012-03-18 14:00
>>20
Can't you just let it go? He proved you wrong, it's a function. Is it that hard to say "all right, I was wrong"? You seem to have some serious issues dude.
Name:
Anonymous2012-03-18 14:00
>>51
And in your case, I really think you need to shut up, and write some actual code.
Name:
Anonymous2012-03-18 14:03
>>52
Okay since you're obviously mentally challenged I will spoon feed you the information.
It's always a function since it outputs "true" only if the element in the set and "false" otherwise, since a set either contains an element or it doesn't it always has a value. Whether it is one to one doesn't matter, it's not a requirement to be a function.
Name:
Anonymous2012-03-18 14:03
>>53
No it isn't. Consider the following case you bitch.
int true = 3;
int false = 2;
And use that in an expression that tests for "true" or "false".
Name:
Anonymous2012-03-18 14:05
>>56
And again, that has nothing to do with the mathematical entity that is a function, try again you stupid piece of shit.
You always keep coming up with these broken situations which never apply to what you're talking about.
Or wait, you don't actually see how this doesn't apply to what we're talking about? Are you seriously this fucking dumb? You're such a fucking retard.
Name:
Anonymous2012-03-18 14:06
>>55 It's always a function since it outputs "true" only if the element in the set and "false" otherwise,
I have a set of unsigned integers. I make true = 3 and false equal = 2. Now I compare a set of data for equality. In this case your statement breaks down.
Name:
Anonymous2012-03-18 14:07
Every time I'm reminded how extremely poorly Kodak understand maths I just lose any respect I might have had for him.
Kodak, stick to programming, you seem to know a little bit of programming, but you keep getting schooled whenever it comes to math.
Name:
Anonymous2012-03-18 14:08
>>57
In such a case it wouldn't be a function. And by the way, the "broken situation" is taken from an optical flow algorithm that we use a my job.
Name:
Anonymous2012-03-18 14:10
>>59
You have zero clue as to what your talking about. I really think you need to learn how "booleans" in your loser languages like C work before you start applying some math model to them.
Name:
Anonymous2012-03-18 14:10
>>58
This isn't even remotely applicable.
You're so god damned confused.
>>58
So what you're saying is that the mathematical entity defined isn't a function because you might define some arbitrary names to some symbols in a programming language?
You're not just retarded, you're deluded.
Name:
Anonymous2012-03-18 14:14
>>63
No it isn't you stupid piece of shit, it has nothing to do with mathematics.
Keep trying to explain yourself though, it's slightly humorous and will continue to be, at least until it becomes tragic.
>>65
Yes it does you dumbass. Now I see why you have no hope as a computer programmer. Man, I think you just need to shut up, step away from this BBS, and write some code.
Name:
Anonymous2012-03-18 14:17
>>56
Let me try to understand this Kodak, you define true to be 3 and false to be 2, your complaint is now that every comparison in C will fall outside of true and false?
In that case the function defined in >>18 applied on the comparisons would return false, since the results are outside of {true, false}, so it's still a function.
Name:
Anonymous2012-03-18 14:17
>>67
First, tell me, have you ever written a non trivial piece of code in your entire life? I bet not. Have you ever read knuth? I bet not.
>>76
Yeah, in this case, it's possible to have 4 and 5 map to "true", and then later one, have 5 map to "false".
Name:
Anonymous2012-03-18 14:27
>>75
The mathematical entity were talking about is a function of the filter set, so if you change the filter set you end up with an entirely different function, but it always returns either true or false.
If you defined it to be a "range" it would always return false in your case cause a comparison in C never returns a range.
Name:
Anonymous2012-03-18 14:28
>>79
You'd end up with a different function, it doesn't change that it always either returns true or false.
Name:
Anonymous2012-03-18 14:29
>>81
In some cases, true would return false and vice versa.
>>82
Yes what is your point? It's still a function.
Listen Kodak, all a function has to do is to return a single value. If you change the definition of a function it's a different function, so for instance if you first let f(x) = 1 and then let f(x) = 2, nothing has been violated, both are still functions. In this case the function is the return value of another function which takes a set to filter against. Consider the FIOC example.
def d(filter_set):
return lambda x : x in filter_set
Now let f = d([2, 3]), given some input f will either return True or False, so it fits the definition of a mathematical function. If you later change f = d([1, 2]), f will return different values for some input compared to the old f, but they're both still functions.
Rightfully you may mutate filter_set after the creation of f so that the same (in the Python sense) function returns different values, but that's not relevant since it's not allowed in the mathematical sense.
Name:
Anonymous2012-03-18 14:39
>>82
Logical negation is a function which has the desired properties, it's even one-to-one.
Name:
Anonymous2012-03-18 14:40
>>84
To sum it up, >>18 has zero clue as to what it's talking about.
Name:
Anonymous2012-03-18 14:42
>>85
There is no logical negation going on though.
Name:
Anonymous2012-03-18 14:44
>>87
Well it would seem that >>83 seems to conclude that the property means that it can't be a function, which isn't true.
X = {1, 2, 3,....,2^n -1} and Y = ("true", "false"}
I can think some C code that would produce the following sequence...
1 -> "true"
2 -> "false"
1 -> "false"
2 -> "true'
3 -> value not in the set
value not in the set -> "true"
Name:
Anonymous2012-03-18 14:51
>>86
Well, >>18 is largely mathematically imprecise so I didn't bother to read the whole post, but if we let Y be a subset of X, and let f:X -> {true, false}, f(x) = true if x is in Y and false otherwise then that defines a valid mathematical function. The definition changes with Y though, so if you change Y the function becomes something different.
It becomes clearer if the definition is changed to something like this, let Y be a subset of X, and let
f_Y:X -> {true, false}, f_Y(x) = true if x is in Y and false otherwise.
Now it's easier to see that f_Y is a different function if you change Y, every f_Y either returns true or false and never both, so they are all functions.
1 -> "true"
2 -> "false"
value not in the set X -> "true"
In such a case, how can this be a function when a value which isn't in a set X, maps to Y ?
Name:
Anonymous2012-03-18 15:02
>>91 In such a case, how can this be a function when a value which isn't in a set X, maps to Y ?
Okay I get you now, yeah you definitely have to expand the domain to something larger than the set you're filtering against, if you don't it just always returns "true" or is undefined.
What >>18 did was to specify that the domain was a superset of the "filter set", which is valid but can probably lead to weird paradoxes with infinite sets and the likes, just saying that the domain is fixed and that the filter set is a subset of that avoids any such problems.
Name:
Anonymous2012-03-18 15:08
>>89
Can we stop keep saying "I can think of some [code] ..." and actually prototype our thoughts correctly?
Name:
Anonymous2012-03-18 15:10
>>93
If you had written any real life code you would've understood what I meant, you no talent bitch.
Name:
Anonymous2012-03-18 15:41
>>94
I'm sorry. I'm only watching this thread because it's marginally interesting - marginally so - but your side of the argument is inserting ambiguity. If it was a matter of "it goes without saying," you wouldn't even be having the argument in the first place. Moreover, I can see what your opposition is saying because they are producing fuller examples, whether or not they are watertight; saying "this is where I start" and "this is what I got from it" is cheating the validity of your argument.
Name:
Anonymous2012-03-18 15:51
>>95
Cripes, look at this idiot, I bet you haven't written a piece of non trivial code in your whole life.
Name:
Anonymous2012-03-18 16:03
Kodak-san, you shouldn't expect math to perfectly fit c. You should instead learn math in its own context, and then apply it as appropriate to c.
>>90
Not everyone here understands the mathematical notation. I did my best to make it unambiguous using plain english, although that is always difficult.
Name:
Anonymous2012-03-18 16:18
Some of the posts here are making me cringe. I stopped when someone claimed functions had to have a one-to-one correspondence.
Name:
Anonymous2012-03-18 16:18
I stopped reading*, that is
Name:
Anonymous2012-03-18 16:22
>>98
That would be Kodak, he's not very bright. He regularly misapplies mathematical concepts because he simply doesn't understand them. He doesn't really know what a subset is but frequently uses the word.
Name:
Anonymous2012-03-18 16:51
>>98
ey is probably just using the wrong terms when trying to say that a function needs to be well defined. That is, that f(x) will take on only one value, for each x. An example of a function that is not well defined is the square root function with no convention for sign:
sqrt(x) = y where y^2 = x
both y and -y could be satisfactory outputs for x. So this definition does not uniquely define what values sqrt must take on for all x, and leaves the function not well defined.
Man this has been entertaining as hell. And also depressing
Name:
Anonymous2012-03-18 17:03
>>101
Right, but >>20 seems to think surjective functions aren't functions either.
Name:
Anonymous2012-03-18 18:08
>>103
Kodak is very unintelligent, this is why he mixes up code with purely mathematical concepts, he somehow thinks that his broken understanding of some programming language can affect mathematics.
He's also unable to admit that he's ever wrong, I've never seen him be right beyond purely basic stuff that everybody knows. There is another thread on /prog/ where he denies that every subset of a countable set is also countable despite mathematical proof being posted in the thread, he attempted to undermine the proof (there were two given actually, both one liners) by showcasing his broken idea of what a subset is and started ranting about credit card numbers or something like that, when confronted about it he angrily responded that nobody had a programming job but him.
So he's not only unintelligent and overly aggressive but he's also unwilling to learn, so I think it's safe to say that he'll never reach the intellectual level of say, you and me. I think it's sad that someone will be stuck at such a low mental level forever, but whatever, it's his fault not mine.
Name:
Anonymous2012-03-18 18:22
>>104
to be fair, it takes more than just an internet argument to learn these things. It takes time and practice, and you need to have access to some good dependable resources. If we linked him to a a good online book on proofs and set theory, ey'd probably learn it pretty quick.
>>105
And I'm still not convinced that you understand, that at least in C, it's possible for a value which is defined outside of a set, to be mapped to a "true" or "false". So perhaps it is you that needs to get a book on set theory. Now tell us all again what you do for a living.
Name:
Anonymous2012-03-18 18:40
>>104
You still don't seem to understand that in language like C, it is possible to have a value, which is defined outside of a set, map to either "true" or "false".
So again, you are stupid. And again, you have no possible future as a computer programmer. Now get rest bitch. You have a long day of doing general labor jobs in the morning.
Name:
Anonymous2012-03-18 18:57
>>108
>it's possible for a value which is defined outside of a set, to be mapped to a "true" or "false"
Are you talking about undefined behavior? Or maybe there is state that affects the output of the function that is not accounted for in the parameters, and depending on what the state is, the function application may evaluate to true or false?
>>115
Eh? Give us another lame math description you no talent bitch.
Name:
Anonymous2012-03-19 13:15
>>108 >>18 is describing a surjective function (domain is some set X, and the value of the function is true if the parameter is a member of X, and false otherwise) yet >>20 is claiming it's not a function. To be fair, it was horribly worded by >>18, but you're still a fucking retard.
Name:
Anonymous2012-03-19 13:16
>>119
Sorry I meant the value of the function is true if the parameter is a member of some set Y which is a subset of X.
Name:
Anonymous2012-03-19 14:31
>>119
If this model is applied to languages that don't have a 'boolean' type, it won't always be a function, since there will be cases when a value not that in the set will map to "true"/"false".
When you say not in the set, you mean not in the domain of the function? That can't happen. By definition, any valid input is a member of the domain. If you mean not in the subset (Y, as I defined earlier), the value of the function will be "false". I don't see what not having a boolean type has to do with it. As long as you can represent "true" and "false", it's fine.
Name:
Anonymous2012-03-19 16:44
>>122 When you say not in the set, you mean not in the domain of the function? That can't happen.
Yes it can. Consider a set of unsigned integers {1...2^n-1} that maps to {true, false} . Now let's say this set undergoes an integral promotion. The end result is a number a outside of {1...2^n-1} would map to 'false'.
Name:
Anonymous2012-03-19 16:49
>>122 I don't see what not having a boolean type has to do with it. As long as you can represent "true" and "false", it's fine.
Having a boolean type gets around having a number outside of a set map to either 'true' or false'.
Hmm...ya know, I think I just lost all the minimum wage taco pushers who like to say "learn basic mathematics".
Name:
Anonymous2012-03-19 16:50
>>122
Kodak is simply too unintelligent to understand mathematics, I suggest you stop trying to teach him, he doesn't know how to listen to his betters.
Name:
Anonymous2012-03-19 16:59
>>122
Listen you mental midget, go work the cash register at target. I bet they appreciate your lame math skills . Also you still haven't posted any code, also you're still a minimum wage worker.
Name:
Anonymous2012-03-19 17:00
>>125
Minimum wage bitch, you still haven't posted any code, you still don't work as aprogrammer.
Name:
Anonymous2012-03-19 17:21
>>125
I'm still not convinced you understand what is being discussed in this thread. Now hush up and go help another customer you no talent bitch.
Name:
Anonymous2012-03-19 17:22
>>127
fuck off and die you cock sucking code monkey piece of shit
You're bringing in details that have no relevance to the mathematical definition you fuckwit. Just because it's possible in an implementation to give an input or return an output that is outside the range doesn't mean the function isn't well-defined. In practice, you would throw an error some way or another if something like that happened (or in this case, just return "false" indicating it isn't a member of the subset). In maths, we don't really consider things like that... but you wouldn't know that, would you?
>>127
Instead of asking for code every ten replies, why don't you open up a fucking calc book.
Name:
Anonymous2012-03-19 18:57
>You're bringing in details that have no relevance to the mathematical definition you fuckwit. Just because it's possible in an implementation to give an input or return an output that is outside the range doesn't mean the function isn't well-defined.
Homegirl, if a number outside of a defined set maps to true/false, then is it a well defined function?
>In practice, you would throw an error some way or another if something like that happened (or in this case, just return "false" indicating it isn't a member of the subset). In maths, we don't really consider things like that... but you wouldn't know that, would you?
You're confused. If the set undergoes an integral transformation, no error will be thrown, because like, ya know, it's a legal conversion.
Name:
Anonymous2012-03-19 22:41
>>133
A function defined from a domain X to a range Y, is well defined if and only if for each x in X, there is a unique y in Y such that f(x) = y.
>>134
The model would still break down in languages that don't support a real boolean type. I'm going to omit integral transformation and numbers outside of a set since we have a bunch of wanna be programmers/wikipedia educated folk on here.
Let's say that I have a set X such that X = {x | 2^n-1 - 1 <= x <= -2^n-1} and a set Y such that Y = {y | y !=0}. Now I define a relation F:X->Y as
F(x) = true when x != 0
If I pick two non zero points a and b in X, it's pretty easy that F(a) = true and F(b) is true. However, I don't think there would be a unique y in Y such that F(x) = y. This because in languages like C, you could possibly end up with f(a) != f(b).
This seems counter intuitive because logic would suggest f(a) == f(b) since they both a and b map to true.
>>133
It doesn't map to anything because it's an invalid input. It would be undefined, but that doesn't mean the function isn't well-defined.
What language does an implicit conversion from a higher precision type to a lower one? If the programmer does an explicit conversion, it's their fault, and yeah, no error would be thrown.
>>137
Like I said before, that's beyond the scope of the maths. The function you defined, f(x), returns "true" if x != 0 and "false" otherwise. A conforming implementation shouldn't return any other value.
Name:
Anonymous2012-03-20 13:19
>>134
You can have a well defined function that doesn't fulfill those requirements, your definition is too strong.
Name:
Anonymous2012-03-20 13:21
>>139
What requirements? That a function shall return the values it is defined to return, or...?