Primes and Squares

@El'endiaStarman This can even be done in O(log n) (assuming n was the size of the set). Finding the minimum of the set is O(log n), so we find the minimum and subtract 1 from both entries.

El'endia Starman

3:15 PM

How is finding the minimum O(log n)?

Sriotchilism O'Zaic

Uh you just follow the left branch down all the way

max is also O(log n)

hackage.haskell.org/package/containers-0.6.2.1/docs/…

Haskell's implementation does this.

El'endia Starman

Ah, you're assuming more structure than I'm giving you.

flawr

@El'endiaStarman are x and y real?

El'endia Starman

@flawr Yes. (Or integer.)

flawr

well you could do (sum(abs(x_i))+1, 0)

this point has certainly no x-coordinate in common with the rest of the points

Sriotchilism O'Zaic

3:24 PM

@El'endiaStarman How so? I mean there are other ways to represent sets, but all of the ones I can think of have a O(log n) minimum function.

El'endia Starman

@SriotchilismO'Zaic A flat list?

Sriotchilism O'Zaic

That's O(1).

Just the first element

El'endia Starman

I didn't say it was sorted.

Sriotchilism O'Zaic

Ok, well this is a particularly bad way to represent sets, but it does kick the order notation up to O(n)

flawr

Isn't O(n) optimal in the sense that you need to even look at each element at least once?

Sriotchilism O'Zaic

3:26 PM

For certain data structures

flawr

So how else would you represent a set of real pairs?

Nathan Merrill

I mean, for certain data structures, it can be O(1). A sorted list of pairs

DJMcMayhem

Aren't red-black-trees common for sets I think?

Or maybe that's maps that I'm thinking of

Sriotchilism O'Zaic

Yep

Self-balancing binary search tree

In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.These structures provide efficient implementations for mutable ordered lists, and can be used for other abstract data structures such as associative arrays, priority queues and sets. The red–black tree, which is a type of self-balancing binary search tree, was called symmetric binary B-tree and was renamed but can still be confused with the generic...

flawr

but then you implicitly assume an ordering

Nathan Merrill

3:29 PM

It's easy to come up with an ordering of pairs of reals.

Sriotchilism O'Zaic

@flawr The ordering can be arbitrary, it is just for internal use.

DJMcMayhem

Ah, yes. std::set is indeed a red-black tree

Sriotchilism O'Zaic

I think Haskells is red black as well.

Feeds

Pac-Man | Design Icons

►

DJMcMayhem

Python sets are hashtables

Sriotchilism O'Zaic

3:31 PM

Oh yeah, I forgot about Hashtables, because they are so bad. This would also be O(n) on hashtables.

flawr

@NathanMerrill I thought it would already be hard to determine whether two reals are distinct:)

DJMcMayhem

@flawr You could argue that a "set" is an abstract data structure, so it has no time-complexity. A (hashtable|heap|array|red-black-tree...) are all "real" data structures, so they each have time-complexities

Nathan Merrill

@SriotchilismO'Zaic I'd argue that hashing is a better implementation, because the average lookup time is O(1), and lookups are more important

flawr

@El'endiaStarman VTC unclear what you're asking=P

Nathan Merrill

I prefer a hash set vs a red/black set pretty much any day. There are reasons to use red/black but for typical use, I find that lookup speed is far more important

El'endia Starman

3:35 PM

@NathanMerrill I was just now thinking along those lines. It's super convenient for Python to include a built-in set implementation, and the default should be a good fit for the most common use-cases.

Sriotchilism O'Zaic

@NathanMerrill Average lookup is not really O(1), it only is with a bunch of assumptions. Lookup is more important for maps, than for sets, sets.

El'endia Starman

@flawr :(

Nathan Merrill

@SriotchilismO'Zaic Isn't the definition of "Average" make a bunch of assumptions?

flawr

It seems now some are talking about a mathematical algorithm while others are talking about an implementation on a computer:)

Nathan Merrill

Like, when we talk about average use cases, we're talking about normal use cases, which makes assumptions.

Sriotchilism O'Zaic

3:36 PM

@NathanMerrill You need additional assumptions like ideal hash functions, which are not mathematically possible

flawr

And assumptions about distributions of the input.

DJMcMayhem

Even "un-ideal" hash functions are going to have very few collisions

Nathan Merrill

@SriotchilismO'Zaic But "good enough" works in O(1) on average.

DJMcMayhem

I guess depending on the resulting length of the hash function

Nathan Merrill

That's the purpose of making averages: You consider typical use cases.

flawr

3:38 PM

I wanna see an o(1) :D

Sriotchilism O'Zaic

@DJMcMayhem It's not really possible to talk about the asymptotic complexity of actual hash sets since they are limited in size. It is better to just say "lookup is fast"

The more important point is that for sets, insertion and deletion are actually more important operations than lookup

Nathan Merrill

@SriotchilismO'Zaic this is fair :)

DJMcMayhem

@SriotchilismO'Zaic I would disagree with that. It entirely depends on what you're using the set for

Sriotchilism O'Zaic

Yes, this is an entirely subjective argument

But I do believe that lookup is less useful.

Also for me an important fact is that hash sets are not a persistent data structure unlike rb trees.

flawr

CMC: Given a finite unsorted list of 2d points, find a point whose distance to its nearest neighbour is maximal in the least possible complexity.

Sriotchilism O'Zaic

3:45 PM

Find the point? i.e. does the point have to be in the list?

flawr

yes it has to be in the list, but it is not necessarily unique

DJMcMayhem

@flawr If it's not unique, wouldn't it's nearest neighbor be the other point with the same coordinates?

Sriotchilism O'Zaic

I think unique in distance to nearest neighbor is meant?

DJMcMayhem

Oh wait I see. The maximal distance doesn't necessarily have to be unique

ninja'd

flawr

Take a regular triangle: any of the three points would be valid as output

DJMcMayhem

3:51 PM

Or any regular polygon (or even a line segment)

El'endia Starman

Regular polygons don't work though?

DJMcMayhem

Why not?

El'endia Starman

Oh, regular in the sense of all sides being the same length, not in the sense of ordinary (like flawr's usage).

Sriotchilism O'Zaic

I think flawr also meant the same sense?

flawr

(and that all points are on the same circle)

El'endia Starman

3:53 PM

Why would you say "regular triangle" and not "equilateral triangle"?

Sriotchilism O'Zaic

shorter? :P

flawr

I didn't remember the word "equilateral", and in polygons ~~they mean the same thing:)~~ regular implies equilateral

El'endia Starman

fiiiiine :P

DJMcMayhem

Wait, can the word "equilateral" apply to other polygons as well? I've only heard it in reference to triangles before

flawr

But I agree, regular is a little bit overused in maths, and it doesn't help that it is a (another) word stolen from regular everyday language

El'endia Starman

3:56 PM

@DJMcMayhem Technically it can, since "equilateral" literally means "same length".

flawr

@DJMcMayhem apparently yes: wikpedia

There are actually quite a few characterizations of quadrilaterals that I was not aware of: en.wikipedia.org/wiki/Template:Polygons

El'endia Starman

4:12 PM

@flawr Woah, same.

Nathan Merrill

4:28 PM

@flawr apparently quadrilateral includes edges that are not straight?

that's odd

El'endia Starman

4:40 PM

@NathanMerrill Are you referring to Lambert and Saccheri quadrilaterals?

Nathan Merrill

yeah

Sriotchilism O'Zaic

They are straight edged.

They are just embedded in Hyperbolic space.

Nathan Merrill

ah ok

El'endia Starman

Well, really, the point of those is to investigate the Parallel Postulate.

Sriotchilism O'Zaic

I guess I should say the curvy looking ones are embedded in a non-euclidean space.

El'endia Starman

4:44 PM

So if you could find a quadrilateral where the sides weren't straight or where three right angles doesn't imply a fourth right angle, then you proved/disproved the Parallel Postulate (depending on your axioms, method of proof, etc).

Nathan Merrill

5:17 PM

Ah, so it's essentially a theoretical shape that was proven to not exist (in euclidean space)

El'endia Starman

Basically, yeah.

Sriotchilism O'Zaic

Yes. The parrallel posulate proves they cannot be in euclidean space.

Transcript for