https://kotlinlang.org logo
Join Slack
Powered by
How about this? ```enum class Direction { NONE...
# getting-started
p
How about this?
Copy code
enum class Direction {
    NONE,
    NORTH, 
    SOUTH, 
    EAST, 
    WEST, 
    START, 
    END;
    
    companion object {
        private val oppositMap = mapOf(
            SOUTH to NORTH,
            NORTH to SOUTH
            // ...
        )
    }

    val opposit get() = oppositMap.getValue(this)
}
z
I would say this one uses null as state and also does lookup every time. Also 
when
solution keeps completnes of enum options in mind.. that is why I would prefer it.
p
You can put all elements to a map
Copy code
private val oppositMap = mapOf(
    SOUTH to NORTH,
    NORTH to SOUTH,
    // ...
    START to NONE,
    NONE to NONE,
)
no 
null
are used, property 
opposit
returns 
Direction
In both solutions lookup is performed every time you access property. In my example it is 
O(1)
because of HashMap. And in your solution complexity of 
when
is 
O(N)
as it goes through all options every time in worst case. But it does not matter for such small numbers 🙂
d
when
on enum compiles to an 
O(1)
lookup.
😍 1
a
And in your solution complexity of 
when
is 
O(N)
as it goes through all options every time in worst case.
Since 
N
is fixed at 7, going through all options is 
O(1)
even if you do it sequentially. 
O(7) = O(1)
But it does not matter for such small numbers
Even if there were a 1000000 options, but always exactly 1000000, it still would be 
O(1)
.
p
when
on enum compiles to an 
O(1)
lookup.
didn’t know that, thanks!
e
Why using a map when you can just use 
when
with enum lol
p
yes, @edwardwongtl, 
when
is better 🙂
r
Another reason for using 
when
is when someone adds a new Direction value, with 
when
you'll get a nice compile time error if you forget to handle the opposite of it, which you won't get with a map
👍 1
@arekolek is that really true? Kind of a question of semantics, but doesn't O(n) where n is the number of options make more sense than saying 
when
is o(1) just because the number of options is not dynamic at runtime?
d
Yes, it is really true. O(n) means the runtime depends linearly on the input. But that is not the case with a chain of say 5 checks. It will always do those 5 steps, regardless of input value. That means O(1)
r
but the performance will still scale O(n) with the number of inputs
you just redefine the number of when checks to not be the input
d
It will scale linearly with the number of options, but those are a compile-time constant. O(n) is about the runtime parameter.
e
nope, 
when
on enum is still O(1) at runtime, the compiler can optimize it
r
I guess that's true, I get a bit thrown off because thinking of scaling at compiletime is pretty odd haha
or wait, do you mean it's o(1) because it's optimized to that?
d
Both
even if it weren't optimized to a lookup table and would just compile to a "if-elseif" chain it would both be O(1)
e
Oh no, 
if
-
else if
chain will not be O(1) man
d
No?
e
If scales linearly with the number of `if`s
d
Actually yes, you are right, it won't
my CS classes are too long ago 🙈
because the first entry of the if-chain will always be faster than the last one
e
Not quite the reason though, its because it has to go through each 
if
checks one by one
a
I think what @Rasmus Franke wrote about the "redefine the number of when checks to not be the input" is close to the truth.
d
If it went to each if check regardless of input that would be O(1)
But because the first enum will only go through one if but the last one will go through all, that's O(N)
a
any
is 
O(n)
but 
listOf(1,2,3,4,5,6, ..., 100000000000000000).any { it > 1000000000000000 }
is 
O(1)
and that's what I meant earlier
even if 
when
was 
O(n)
, the code that used it would be 
O(1)
because the number of branches was fixed in advance
r
what is even n in this scenario?
i don't think we have one and that's why it's a bit weird
a
if we are analysing time complexity of 
when
, then 
n
is the number of branches
d
No, it is not. It is the input parameter to 
when
.
r
in that case, assuming the compiler doesn't optimize it to go right to the correct branch, wouldn't we see 
when
as o(n)?
a
but 
when
doesn't require an "input parameter"
you can inline it in branches
r
I really think you have to define 
n
to make any sense of complexity, and both o(1) and o(n) can be correct here depending on you refer to the constant argument we put into 
when
or if you refer to the number of branches
a
but if we are analysing code like:
Copy code
when (x) {
   1 ->
   2 ->
   3 ->
}
Then it doesn't have any input, so there's no 
n
, and the time complexity of this snippet is 
O(1)
d
x
is the input.
a
@arekolek why is 
listOf(1, 2, ....).any { it > 10000}
O(1)
?
d
If that compiles to 3 if statements, that's O(N), because 3 takes 3 instructions, and 1 takes 1 instruction. if it compiles to a lookup, all inputs (1, 2 or 3) only take the one instruction (the lookup)
r
any
shouldn't be O(1) there, only the list creation
uh maybe not even the list creation..?
again, we really have to define exactly what factor is scaling or not
b
For enums with a very small number of constants, the JIT will often still compile lookup tables to if-else under the hood https://stackoverflow.com/questions/15621083/why-does-java-switch-on-contiguous-ints-appear-to-run-faster-with-added-cases
a
@Andreas Sinz in other words:
Copy code
fun myAny() = listOf(1,2,3,4,5,6, ..., 100000000000000000).any { it > 10000 }

fun test1(n: Int) {
    val x = myAny()
    val list = mutableListOf<Boolean>()
    repeat(n) {
        list += x
    }
    return list
}

fun test2() = test1(123456)
* myAny is O(1) * test1 is O(n) * test2 is O(1)
even though 
test1
uses 
any
which itself is 
O(n)
(where 
n
is the length of the list it works on), what 
test1
passes to 
any
is independent of the 
test1
input
r
that makes sense, because n is not the same thing in test1 and test2
but an interesting question is, should we even define 
O
when 
n
doesn't exist?
it could never be anything but 
O(1)
because what would it even scale with
a
if there's no input and the program is deterministic, then it is 
O(1)
I think, always finishes in the same, predetermined number of steps
on the other hand you could have multiple input parameters, like for graph algorithms, and then you often speak of times like O(n+m) for example
👍 1
5 Views
Open in Slack
PreviousNext
Powered by