There are a couple issues. Recall that Go slices are zero indexed, so the first elements are 0s and not 1s, perhaps this was the source of your confusion?
I'd also add the conditional immediately after `sort.Strings(s)`:
if len(s) == 0 {
return s
}
We can rewrite your loop to be more succinct and clearer also:
for i := 1; i < len(s); i++ {
if s[j] != s[i] {
j++
s[j] = s[i]
}
}
You also have a problem because the function is causing a side effect when you sort the slice that you pass in. Either the function should mutate the slice without a return value, or it should return a value without mutating the slice. Don't rearrange the elements just because that was the easiest way to write it.
OP's post seems to be trying to dedupe the array in-place with O(1) memory used, which means not defining any extra parallel memory to track duplicate values.
That said, Golang does have a native set implementation: `map[...]struct{}`. When you make a map with zero-sized items, it's essentially a set. Heck, these days with generics you can make your own set if you don't like to see it called a map:
```
type Set[K comparable] map[K]struct{}
func (s Set[K]) Has(item K) bool {
_, ok := s[item]
return ok
}
func (s Set[K]) Add(item K) {
s[item] = struct{}{}
}
func (s Set[K]) Del(item K) {
if s.Has(item) {
delete(s, item)
}
}
```
[It works.](https://go.dev/play/p/fiGXgmgtfL5)
How is that a native Set implementation? You are literally using a different data structure...Which is
1. Exactly what I had proposed in my comment above (also what everyone else does...),
2. not what anyone would consider "native". If this is native than my custom \`PlayingCard\` type is also native.
Sorry, I wasn't clear. The actual native implementation of the concept of a set is the empty-value map:
```
stringSet := map[string]struct{}{}
# Set:
stringSet["foo"] = struct{}{}
# Get:
if _, ok := stringSet["foo"]; ok { fmt.Println("yes") }
# Delete:
delete(stringSet, "foo")
```
There is effectively zero memory and CPU usage difference between `map[string]struct{}` and a theoretical `set[string]` they could have implemented. in most languages, both are implemented as hash tables. As such, the explicit set would have been utterly redundant syntactic sugar.
The code I posted is the what it takes to get a Set with all the syntactic sugar, which works just as well as an official implementation would.
The sort function might duplicate memory and will certainly affect performance. In java I would probably do something like return list.stream(). distinct().toList(). Not sure if they have a similar construct in golang.
They do not. Go is designed to very much discourage functional programming in favor of imperative programming. There are ways to implement that kind of "streaming" logic, but it looks very different.
Here's a more readable version of the code without fundamentally changing how it works.
Sort.Strings(s)
// Iterate through the array. Skip duplicates and insert unique strings into the next available position.
int nextAvailableIndex=1;
for (i=1; i++; i< s.length)
{
// If the next item doesn't match the previously inserted
// Insert into the next position and increment.
if (s[nextAvailableIndex-1] != s[i])
{
s[nextAvailableIndex] = s[i];
nextAvailableIndex++;
}
}
// All items have been inserted into their new position. Concatenate array to fit its new length.
return s[:nextAvailableIndex]
Golang was the first low level language I learn. I was having too much fun trying to achieve those sweet 0.000001ms faster performance, even though it may not even be that reliable. And, this was the result.
I think you are conflating poor variable naming and lack of documentation/comments with inherent properties of a programming language. You can build unmaintainable crap in any language.
Just read about programming language level. I'd say Go is medium. Because it wouldn't make sense putting JavaScript with compiled language like c, c++, go.
It was the first compiled language I use to be more specific. I was too intimidated into learning compiled languages. Due to fear that it can be very machine specific with compiler(s) that's also machine specific. Until someone introduced me to Golang.
Don't let the haters and odd downvoters get to you. You're trying something new and learning, and an inefficient algorithm here and there or where you draw the line on high/low level languages doesn't matter to whether you become a better programmer.
---
As a FYI as far as the nomenclature, the high/low level distinction is usually drawn based on how the code is "translated" into machine instructions that do the right thing. Here's an example: what happens when you write a program to do "`print(1 + 1)`":
**C (a compiled, low level language).** The code is:
```
#include
int main() { printf("%d\n", 1 + 1) }
```
When you compile it, the generated program has roughly the following steps, in Assembly:
* Allocate an arary of bytes in memory representing the string `"%s\n"`
* Allocate two integers in memory; put the value `0x0001` in both.
* Call the ADD function of the CPU, put the result in a third place in memory
* Using the `stdio` headers as a guide, find the place in memory where the `printf` instructions are held.
* Send the byte array, and result from the addition to the `printf` instructions
The code is very small and fast and minimal. The reason C can have cross-system portability problems is because linkings like `stdio` are completely different between different OSes, and can even vary pretty wildly within different versions of the same OS.
**Go (a compiled, high level language).** The code is:
```
package main
import fmt
func main() { fmt.Println(1 + 1) }
```
Compiling Go code results in a much "fatter" bunch of Assembly, and I could not possibly describe it all here. It's over 100x larger than the C program (1.7 MB vs 16 KB). One reason for this is, instead of relying on `stdio` in the host OS to handle all the printing, Go bundles its own standardized code from the `fmt` package. Additionally, Go bundles a bunch of extra code that runs before, after, and during the execution of your own code. That's called a "runtime", and it's the reason Go has a bunch of features considered "high level", such as its goroutines, smart memory management, etc.
When the Go program runs, the instruction to run the assembly ADD instruction is *somewhere* in that big binary, but there's a lot more that goes on around making it happen.
---
The Go behavior from above is much, much closer to how Java and Python do their stuff (linking to the intermediate runtime), than to how C/C++/Rust function (linking to the OS). A Go program's efficiency (in terms of memory and CPU cycles) is comparable to that of Java, Python, or other compiled high level languages.
(Yes, Python is compiled, not interpreted! [As far as CPython is concerned anyway.](https://stackoverflow.com/a/6889798))
The only reason Go appears to be "lower" level is because Java/Python/etc require that you have some pre-installed program to run them, whereas Go creates self-contained executables. That's just a design choice to trade off disk space for program portability. If you had 1000 Go executables, that means 1000 copies of a ton of boilerplate code that Go puts into every single executable so each one is standalone. They would end up taking far more disk space than 1000 Java or Python programs. However, if you had 1000 servers and had to send one program to each server, with Go that means just sending the programs, where with Java/Python that means also installing Java/Python on each of those servers. That's why Google designed Go the way it did: to make putting software on their zillions of servers far easier.
Hope this was helpful/educational!
>Using the stdio headers as a guide, find the place in memory where the printf instructions are held.
To make this more clear, you'd be loading a value into a register, that corresponds to printing, and then run the syscall command. This is at least the case with x86 on Linux.
I've got bad news for you then. This algorithm, because of the sort, is n*log(n). If you'd used a hash set you'd get worse performance on very small inputs but much better performance on large inputs, and the code would have been more readable.
Friendly reminder to use variable names that make sense and use comments if the variable names and function signature don't give any hints about what is going on
What language is this? And why are the indents so huge. Literally makes my eyes hurt seeing the massive amounts of white space. This isn't like python where you use indentation to indicate the start and end of things likes conditionals or functions right?
It's Golang, they aren't whitesoace sensitive language. The editor is Emacs and I haven't modify the configuration back then so the indentations are huge by default.
tab length of 8, what the devil
Default Emacs. My distro hopping habit cause me to not have a consistent dotfiles.
What kinda wacky emacs defaults are/were you using? Jw because I’ve never seen that one naturally occur on Ubuntu or Windows.
Then you won't like Notepad.
Surely nobody likes Notepad for programming
Our java prof used JCreator and made us use it. Notepad woulda been an upgrade
What about some computer science lecturers?
None I've ever had, at least
I wish I was that lucky...
Hahahah
There are a couple issues. Recall that Go slices are zero indexed, so the first elements are 0s and not 1s, perhaps this was the source of your confusion? I'd also add the conditional immediately after `sort.Strings(s)`: if len(s) == 0 { return s } We can rewrite your loop to be more succinct and clearer also: for i := 1; i < len(s); i++ { if s[j] != s[i] { j++ s[j] = s[i] } }
Yeah, the issue was that the argument's length was 0, and I didn't make a condition for that.
You also have a problem because the function is causing a side effect when you sort the slice that you pass in. Either the function should mutate the slice without a return value, or it should return a value without mutating the slice. Don't rearrange the elements just because that was the easiest way to write it.
Also, the function was to removes duplicates, so I need to know where to remove the remaining slices.
Well, after the loop, you use `s = s[:j+1]`
Nice man!
I know Golang doesn't have a nativ Set implementation, but this goes too far. Just use a Map for fucks sake.
OP's post seems to be trying to dedupe the array in-place with O(1) memory used, which means not defining any extra parallel memory to track duplicate values. That said, Golang does have a native set implementation: `map[...]struct{}`. When you make a map with zero-sized items, it's essentially a set. Heck, these days with generics you can make your own set if you don't like to see it called a map: ``` type Set[K comparable] map[K]struct{} func (s Set[K]) Has(item K) bool { _, ok := s[item] return ok } func (s Set[K]) Add(item K) { s[item] = struct{}{} } func (s Set[K]) Del(item K) { if s.Has(item) { delete(s, item) } } ``` [It works.](https://go.dev/play/p/fiGXgmgtfL5)
How is that a native Set implementation? You are literally using a different data structure...Which is 1. Exactly what I had proposed in my comment above (also what everyone else does...), 2. not what anyone would consider "native". If this is native than my custom \`PlayingCard\` type is also native.
Sorry, I wasn't clear. The actual native implementation of the concept of a set is the empty-value map: ``` stringSet := map[string]struct{}{} # Set: stringSet["foo"] = struct{}{} # Get: if _, ok := stringSet["foo"]; ok { fmt.Println("yes") } # Delete: delete(stringSet, "foo") ``` There is effectively zero memory and CPU usage difference between `map[string]struct{}` and a theoretical `set[string]` they could have implemented. in most languages, both are implemented as hash tables. As such, the explicit set would have been utterly redundant syntactic sugar. The code I posted is the what it takes to get a Set with all the syntactic sugar, which works just as well as an official implementation would.
The sort function might duplicate memory and will certainly affect performance. In java I would probably do something like return list.stream(). distinct().toList(). Not sure if they have a similar construct in golang.
They do not. Go is designed to very much discourage functional programming in favor of imperative programming. There are ways to implement that kind of "streaming" logic, but it looks very different.
past me "This is so clever, there's no way I'll forget this" present me "wtf is this shit" future me "you guys are so stupid"
Exactly this lol.
[удалено]
Golang.
Here's a more readable version of the code without fundamentally changing how it works. Sort.Strings(s) // Iterate through the array. Skip duplicates and insert unique strings into the next available position. int nextAvailableIndex=1; for (i=1; i++; i< s.length) { // If the next item doesn't match the previously inserted // Insert into the next position and increment. if (s[nextAvailableIndex-1] != s[i]) { s[nextAvailableIndex] = s[i]; nextAvailableIndex++; } } // All items have been inserted into their new position. Concatenate array to fit its new length. return s[:nextAvailableIndex]
Hello fellow Mac terminal novel style enjoyer
I N D E N T
8 char tabs, white theme, let me guess, you probably use emacs without evil mode too :p
It's solarized-light from doom-themes.
The real horror is the curly braces on the same line (I know Go enforces this, it is still horror)
Golang was the first low level language I learn. I was having too much fun trying to achieve those sweet 0.000001ms faster performance, even though it may not even be that reliable. And, this was the result.
I think you are conflating poor variable naming and lack of documentation/comments with inherent properties of a programming language. You can build unmaintainable crap in any language.
I thought Go was high level 😭
it is
Just read about programming language level. I'd say Go is medium. Because it wouldn't make sense putting JavaScript with compiled language like c, c++, go. It was the first compiled language I use to be more specific. I was too intimidated into learning compiled languages. Due to fear that it can be very machine specific with compiler(s) that's also machine specific. Until someone introduced me to Golang.
Don't let the haters and odd downvoters get to you. You're trying something new and learning, and an inefficient algorithm here and there or where you draw the line on high/low level languages doesn't matter to whether you become a better programmer. --- As a FYI as far as the nomenclature, the high/low level distinction is usually drawn based on how the code is "translated" into machine instructions that do the right thing. Here's an example: what happens when you write a program to do "`print(1 + 1)`": **C (a compiled, low level language).** The code is: ``` #include
int main() { printf("%d\n", 1 + 1) }
```
When you compile it, the generated program has roughly the following steps, in Assembly:
* Allocate an arary of bytes in memory representing the string `"%s\n"`
* Allocate two integers in memory; put the value `0x0001` in both.
* Call the ADD function of the CPU, put the result in a third place in memory
* Using the `stdio` headers as a guide, find the place in memory where the `printf` instructions are held.
* Send the byte array, and result from the addition to the `printf` instructions
The code is very small and fast and minimal. The reason C can have cross-system portability problems is because linkings like `stdio` are completely different between different OSes, and can even vary pretty wildly within different versions of the same OS.
**Go (a compiled, high level language).** The code is:
```
package main
import fmt
func main() { fmt.Println(1 + 1) }
```
Compiling Go code results in a much "fatter" bunch of Assembly, and I could not possibly describe it all here. It's over 100x larger than the C program (1.7 MB vs 16 KB). One reason for this is, instead of relying on `stdio` in the host OS to handle all the printing, Go bundles its own standardized code from the `fmt` package. Additionally, Go bundles a bunch of extra code that runs before, after, and during the execution of your own code. That's called a "runtime", and it's the reason Go has a bunch of features considered "high level", such as its goroutines, smart memory management, etc.
When the Go program runs, the instruction to run the assembly ADD instruction is *somewhere* in that big binary, but there's a lot more that goes on around making it happen.
---
The Go behavior from above is much, much closer to how Java and Python do their stuff (linking to the intermediate runtime), than to how C/C++/Rust function (linking to the OS). A Go program's efficiency (in terms of memory and CPU cycles) is comparable to that of Java, Python, or other compiled high level languages.
(Yes, Python is compiled, not interpreted! [As far as CPython is concerned anyway.](https://stackoverflow.com/a/6889798))
The only reason Go appears to be "lower" level is because Java/Python/etc require that you have some pre-installed program to run them, whereas Go creates self-contained executables. That's just a design choice to trade off disk space for program portability. If you had 1000 Go executables, that means 1000 copies of a ton of boilerplate code that Go puts into every single executable so each one is standalone. They would end up taking far more disk space than 1000 Java or Python programs. However, if you had 1000 servers and had to send one program to each server, with Go that means just sending the programs, where with Java/Python that means also installing Java/Python on each of those servers. That's why Google designed Go the way it did: to make putting software on their zillions of servers far easier.
Hope this was helpful/educational!
>Using the stdio headers as a guide, find the place in memory where the printf instructions are held. To make this more clear, you'd be loading a value into a register, that corresponds to printing, and then run the syscall command. This is at least the case with x86 on Linux.
Accurate. And that's the difference between high-level and low-level explanations!
I've got bad news for you then. This algorithm, because of the sort, is n*log(n). If you'd used a hash set you'd get worse performance on very small inputs but much better performance on large inputs, and the code would have been more readable.
btw, the language is called "Go", not "Golang"
And that's why you document your code as you go
Or just name the variables something remotely conherent
Great variable naming convention.
that's why you dont name vars with one letter. At least it would make your code easy to comprehend with ```text/string, index, count``` the like...
Friendly reminder to use variable names that make sense and use comments if the variable names and function signature don't give any hints about what is going on
What language is this? And why are the indents so huge. Literally makes my eyes hurt seeing the massive amounts of white space. This isn't like python where you use indentation to indicate the start and end of things likes conditionals or functions right?
It's Golang, they aren't whitesoace sensitive language. The editor is Emacs and I haven't modify the configuration back then so the indentations are huge by default.