c/programmer_humor · by qaz@lemmy.world · 301d

Who cares about time complexity

457 points · 68 comments · view on lemmy.world

68 Comments

theunknownmuncher@lemmy.world · 120 pts · 301d (4 replies)

Whenever you sit back and smile proudly to yourself about how clever the block of code you just wrote is, your next move should be to delete and rewrite it.

This is a clever block of code! Great job, now rewrite it to be sane 😂

balsoft@lemmy.ml · 32 pts · 301d (3 replies)

I think it depends; some smart code is good actually, think 0x5f3759df. As long as you properly document it and leave plenty of comments. This one is not smart though, at best it's what I would call witty.

theunknownmuncher@lemmy.world · 23 pts · 301d

I'd accept that "smart code" and "clever code" are 2 different things

Valmond@lemmy.world · 12 pts · 301d

Fast inverse square root eh?

Cethin@lemmy.zip · 4 pts · 301d

This isn't smart. This is clever. It's a way to solve a problem in a novel way. It isn't the best, or even most obvious, way to solve the problem. It's just interesting.

douglasg14b@lemmy.world · 68 pts · 301d (14 replies)

Still linear time at least, could always be much MUCH worse

dfyx@lemmy.helios42.de · 44 pts · 301d (3 replies)

There could be a hidden quadratic cost because the string needs to be reallocated and copied multiple times.

Jerkface@lemmy.world · 44 pts · 301d (1 reply)

Not if I don't see it.

aaaaaaaaargh@feddit.org · 11 pts · 301d

This is the spirit

kogasa@programming.dev · 5 pts · 301d

Not quadratic in the length of the input. Assuming replace is linear this is also linear

lugal@lemmy.dbzer0.com · 17 pts · 301d (9 replies)

True. Lost opportunity to blow things up with useless recursivity

bleistift2@sopuli.xyz · 17 pts · 301d (8 replies)

The word you’re looking for is recursion (see recursion).

Gonzako@lemmy.world · 6 pts · 301d (6 replies)

Nah, I'd like to un-see recursion. It was way overblown on uni, I barely ever use it.

Cethin@lemmy.zip · 10 pts · 301d (5 replies)

Recursion is amazing for a small selection of problems. Most of the time you don't need, or want, it. When it is useful though, it tends to be really useful.

I don't understand people's issue with it. I always found it easy. Maybe that's why I feel this way. Maybe if you find it challenging you want to avoid it, even when it's a good solution.

Ephera@lemmy.ml · 4 pts · 301d (1 reply)

I think, their point (and also my experience) is that you get taught about it in university a lot more than about simple loops, so it feels more important even though you rarely use it in reality.

Same thing goes for linked lists and inheritance...

embed_me@programming.dev · 3 pts · 300d

Linked lists are encountered somewhat frequently in low level systems programming.

kamstrup@programming.dev · 4 pts · 300d (1 reply)

Most devs I know like recursion. Trouble is that many popular languages don't support tail recursion, but throw a stackoverflow error after a few thousand levels. So you have to keep track of max recursion depth manually, and it starts to look like a complicated solution

dejected_warp_core@lemmy.world · 2 pts · 288d

You mean, like this?

kamstrup@programming.dev · 1 pts · 301d

lugal@lemmy.dbzer0.com · 5 pts · 301d

Thanks. I knew something was off

CookieOfFortune@lemmy.world · 65 pts · 301d (1 reply)

This isn’t sufficiently enterprisey for Java. There should be a Roman numeral factory followed by relevant fromString and toInteger methods.

vithigar@lemmy.ca · 15 pts · 301d

Ugh. Literally refactored multiple factories into straightforward functions in the most recent sprint where I work.

Someone saw a public factory method which was a factory for a reason and just cargo culted multiple private methods using the same pattern.

anugeshtu@lemmy.world · 41 pts · 301d (1 reply)

Why don't you just ask Chat-GPT o3 every time? Works like a charm!

lugal@lemmy.dbzer0.com · 47 pts · 301d

Because there are better random generators

TootSweet@lemmy.world · 31 pts · 301d

My first thought was something along the lines of a "zip bomb". For every "M" in the input string, it'd use more than a KiB of memory. But still, it'd take a string of millions of "M"s to exhaust memory on even a low-end modern server. Still probably not a good idea to expose to untrusted input on a public networked server, though. And it could easily peg a CPU core for a good while. Very good leveraged target for DDOSing.

rooroo@feddit.org · 22 pts · 301d (13 replies)

It also works the other way round: wanna convert Arabic n to Roman? Just write n times ‘I’ and revert these replacement in inverse order.

lugal@lemmy.dbzer0.com · 7 pts · 301d (12 replies)

I don't know what happens when the substring overlaps. Like for the number 6, will it replace the first 5 I's with V and end up correctly with VI or the last ones and come to IV? I would guess the former and maybe you know but I never thought about it before

Atlas_@lemmy.world · 6 pts · 301d (2 replies)

Also does not handle 'IIIIIIIII' -> 'IX' properly

pitiable_sandwich540@feddit.org · 3 pts · 301d (1 reply)

If the substitution went right to left it might work.

rooroo@feddit.org · 2 pts · 300d

It does.

rooroo@feddit.org · 2 pts · 300d (8 replies)

I’ve written it that way and it works, as in it will replace left to right and you replace iiii to iv after iiiii to v

lugal@lemmy.dbzer0.com · 0 pts · 300d (7 replies)

Makes sense but it will fail at 9 (VIV) it would only work for 9 if the replace went from right to left or the V and IV statements were exchanged but in both cases, 6 would fail

rooroo@feddit.org · 1 pts · 300d (6 replies)

9 is IX though, and that works.

6 works fine, as it replaces the first set of 5 I with V and then there’s nothing to replace.

I’d written it in typescript for all it’s worth; go ahead and try it yourself :)

lugal@lemmy.dbzer0.com · 1 pts · 300d (5 replies)

Does 9 really work? Wouldn't it be:

IIIIIIIII
-> VIIII
-> VIV

rooroo@feddit.org · 2 pts · 299d

I like your questions about this and they all seem fair but I kinda wanna encourage you to go ahead and write it yourself; it’s a fun way to convert into Roman numerals that both is and isn’t intuitive at the same time.

rooroo@feddit.org · 2 pts · 299d (3 replies)

No, cause you do the replacement from large to small, I.e. you’d first check for 10 I to replace with X (none found); then replace 9 with IX (check), then check for 5, 4 and so on.

lugal@lemmy.dbzer0.com · 2 pts · 299d

The original doesn't have an extra check for 9 and it works for Roman->Indioarabic because it's:

IX
->IVV
->IIIIV
->IIIIIIIII

But the other way around, you need an extra step for 9. That's where our misunderstanding comes from.

rooroo@feddit.org · 1 pts · 299d

I noticed my “and so on” is literally a noop here so yeah.

TheLazyNerd@europe.pub · 20 pts · 300d

Since Roman numerals have an upper bound, the time complexity is always O(1).

Zangoose@lemmy.world · 14 pts · 301d (1 reply)

They forgot "CM" so this doesn't work for any number that ends in 900s

trxxruraxvr@lemmy.world · 50 pts · 301d

No, M will be replaced by DD and then CD will be picked up, so it will go

CM
CDD
CCCCD
CCCCCCCCC
......

olafurp@lemmy.world · 9 pts · 300d (1 reply)

It's not too bad, it's readable and easily optimised by adding intermediate sums and removing whatever power of 10 you're working on.

nik9000@programming.dev · 2 pts · 300d

My first thought was that it'd be a great oracle for randomized testing.

eah@programming.dev · 8 pts · 301d (6 replies)

It's got some code duplication. Who can code ~~gulf~~ golf this?

tourist@lemmy.world · 48 pts · 301d

public static int convertRomanNumeral(String numeral) {
    return 4; // todo
}

grue@lemmy.world · 27 pts · 301d (1 reply)

Code gulf, you say?

public static String
convertRomanNumeral(String numeral) {
    numeral = numeral.replace("America", "Mexico");
    return numeral;
}

deadbeef79000@lemmy.nz · 5 pts · 300d

Gulf clap.

ray@sh.itjust.works · 3 pts · 301d (1 reply)

public static int convertRomanNumeral(String numeral)
{
  numeral = numeral.replace("M", "DD")
    .replace("CD", "CCCC")
    .replace("D", "CCCCC")
    .replace("C", "LL")
    .replace("XL", "XXXX")
    .replace("L", "XXXXX")
    .replace("X", "VV")
    .replace("IV", "IIII")
    .replace("V", "IIIII");
  return numeral.length();
}

qaz@lemmy.world · 7 pts · 301d

public static int convertRomanNumeral(String numeral)
{
  return numeral.replace("M", "DD")
    .replace("CD", "CCCC")
    .replace("D", "CCCCC")
    .replace("C", "LL")
    .replace("XL", "XXXX")
    .replace("L", "XXXXX")
    .replace("X", "VV")
    .replace("IV", "IIII")
    .replace("V", "IIIII")
    .length();
}

TheLazyNerd@europe.pub · 2 pts · 300d

I'm not too good with java, but it should be something like this:

public static int convertRomanNumeral(string n){Map.of("M","DD","CD","CCCC","D","CCCCC","C","LL","XL","XXXX","L","XXXXX","X","VV","IV","IIII","V","IIIII");.forEach((k,v)->{n=n.replace(k,v);});return n.length();}

SpaceNoodle@lemmy.world · 7 pts · 301d (3 replies)

IIV becomes IIIII, hm?

trxxruraxvr@lemmy.world · 33 pts · 301d (2 replies)

IIV would never be used. In Roman numerals at most one smaller unit can come in front of a larger one. The code doesn't do any validation though.

Mirodir@discuss.tchncs.de · 14 pts · 301d

While it doesn't say anything about IIV specifically, they sure got creative enough to sometimes subtract more than one of the smaller units from a larger one.

SpaceNoodle@lemmy.world · -6 pts · 301d

Yes, that does demonstrate my point.

panda_abyss@lemmy.ca · 6 pts · 301d (2 replies)

Should do a regex find all then iterate over each chunk recursively until unchanged.

ZTechnical@programming.dev · 9 pts · 301d (1 reply)

there was no regex in ancient rome

felbane@lemmy.world · 6 pts · 301d

Actually there were seven kings prior to the establishment of the republic, at which point they expelled the rulers... a reg-ex if you will.

Wynnstan@lemmy.world · 6 pts · 300d

Alternatively pip install roman.

fckreddit@lemmy.ml · 5 pts · 301d (1 reply)

I just wrote something similar for decoding binary asm instructions.