• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 17:41
CEST 23:41
KST 06:41
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL19] Finals Recap: Standing Tall9HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
[BSL20] Non-Korean Championship 4x BSL + 4x China1Flash Announces Hiatus From ASL63Weekly Cups (June 23-29): Reynor in world title form?13FEL Cracov 2025 (July 27) - $8000 live event22Esports World Cup 2025 - Final Player Roster16
StarCraft 2
General
Program: SC2 / XSplit / OBS Scene Switcher The SCII GOAT: A statistical Evaluation Statistics for vetoed/disliked maps Weekly Cups (June 23-29): Reynor in world title form? PiG Sty Festival #5: Playoffs Preview + Groups Recap
Tourneys
RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event Sparkling Tuna Cup - Weekly Open Tournament WardiTV Mondays Korean Starcraft League Week 77
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
SC uni coach streams logging into betting site Player “Jedi” cheat on CSL Flash Announces Hiatus From ASL BW General Discussion Practice Partners (Official)
Tourneys
[BSL20] Non-Korean Championship 4x BSL + 4x China CSL Xiamen International Invitational The Casual Games of the Week Thread [BSL20] Grand Finals - Sunday 20:00 CET
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Path of Exile Stormgate/Frost Giant Megathread Nintendo Switch Thread What do you want from future RTS games? Beyond All Reason
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread Summer Games Done Quick 2025! Trading/Investing Thread Things Aren’t Peaceful in Palestine
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
Blogs
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 617 users

The Big Programming Thread - Page 727

Forum Index > General Forum
Post a Reply
Prev 1 725 726 727 728 729 1031 Next
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.
Mr. Wiggles
Profile Blog Joined August 2010
Canada5894 Posts
May 06 2016 04:40 GMT
#14521
It seems like the problem is well-studied:

https://en.m.wikipedia.org/wiki/Nearest_neighbor_search

Based on your description, I also thought of maybe using some kind of tree structure in order to get faster search, and it turns out there's quite the selection:

https://en.m.wikipedia.org/wiki/Metric_tree

I also liked:

https://en.m.wikipedia.org/wiki/Ball_tree

It seems like the correct choice of algorithm here depends a lot on the application as well. For example, the number of dimensions, choice of distance, whether the search structure can be constructed offline or needs online updates, whether you need an exact or good-enough answer, etc.

Thanks for the reading distraction today!
you gotta dance
meadbert
Profile Blog Joined October 2010
United States681 Posts
May 06 2016 15:46 GMT
#14522
I have had to do this and here is how I did it:

First you want to cluster the data. Basically loop through all of your elements and any time you come to an element that is "far" from all other "captains" make that guy a captain. When you are done you will have some number of captains. Then assign everyone else to the nearest captain. Each captain should have a sorted list of elements where the closest elements come first and the furthest later. You can do this hierarchically and each level of hierarchy down you redefine far so that more and more elements are far.

When you want to find the nearest element you simply loop over all the captains and then find the nearest captain.
Then loop over elements near that captain and find the nearest element. This gives you a pretty good answer that still might not be the best. Now you must loop over all the other captains. From those captains you can skip the vast majority of their elements based on this information.

T = Target
B = Best so Far
D = Best Captain (May not be best's Captain)
C = Current Captain
X = Elements in Current Captain

BT = Distance between Best and Target
CD = Distance between Current Captain an Best Captain
etc

First of all we know that CX < DX because otherwise those elements in C would have been put in D.

Sometimes we can skip the whole Captain:

if (BT + DT < CD/2) then we know that we can safely skip the Current Captain C because any element closer to T than B would have also been closer to D than C so it would not be in C.

If we cannot skip C altogether then we must traverse into hierarchically, or if it is a leaf node with a sorted list of elements we need only consider elements X such that:

CX > CT - BT
Hhanh00
Profile Joined May 2016
34 Posts
May 07 2016 02:59 GMT
#14523
If you (OP) are looking for a way to find the closest element based on a given metric it seems that you have a pretty good algo. However, maybe what you actually want is different. I'd like to group my data to find clusters of similar results and then have the distance towards their centers (like what the previous poster suggested).
It's area of research in machine learning: https://en.wikipedia.org/wiki/Cluster_analysis
There are many algorithms and the classic ones are well implemented. They will handle million of records easily.
Shield
Profile Blog Joined August 2009
Bulgaria4824 Posts
Last Edited: 2016-05-07 10:35:27
May 07 2016 10:35 GMT
#14524
I've quickly checked some of Boost's source files and they use ifdef for Windows as expected. Is this how libraries like Boost achieve cross-platform solution?
Manit0u
Profile Blog Joined August 2004
Poland17243 Posts
Last Edited: 2016-05-07 15:33:01
May 07 2016 15:17 GMT
#14525
Ok, I think I got around to finishing my irange and arange functions in C but I've run into a problem compiling them... I really forgot how to do that

+ Show Spoiler [code] +


//main.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "arange.h"
#include "irange.h"

int main(void)
{
int_range_t *int_range = irange(1, 5);
char_range_t *char_range = arange('a', 'f');

puts("Int range:\n");

for (int i = 0; i < int_range->length; i++) {
printf("%d", int_range->nums[i]);
}

puts("Char range:\n");

for (int i = 0; i < char_range->length; i++) {
printf("%c", char_range->chars[i]);
}

free(int_range);
free(char_range);

return 0;
}



//arange.h
#include <stdlib.h>
#include <stdbool.h>

/* Definitions */
typedef struct char_range_s char_range_t;

/* Prototypes */
char_range_t *arange(char start, char end);
bool is_valid_letter(char input);



//arange.c
#include "arange.h"

typedef struct char_range_s {
int length;
char chars[];
} char_range_t;

/*
* Function : arange
* Arguments: char start - initial char, char end - final char
* (if start > end the range will be in descending order,
* only letters are supported)
* Returns : char_range_t or NULL
* Notes : The caller has to free the allocated memory
*/
char_range_t *arange(char start, char end)
{
if (!is_valid_letter(start) || !is_valid_letter(end)) {
return NULL;
}

char c;
int istart = start - '0';
int iend = end - '0';
bool reverse = (iend < istart);
int size = (reverse ? istart - iend : iend - istart) + 1;
size_t mem = sizeof(char_range_t) + size * sizeof(char);
char_range_t *range = malloc(mem);

if (range == NULL) {
return NULL;
}

range->length = size;

for (int i = 0; i < size; i += 1) {
c = reverse ? istart - i : istart + i;
range->chars[i] = c;
}

return range;
}

bool is_valid_letter(char input)
{
int val = input - '0';

if ((val >= 65 && val <= 90) || (val >= 97 && val <= 122)) {
return true;
}

return false;
}



//irange.h
#include <stdlib.h>
#include <stdbool.h>

/* Definitions */
typedef struct int_range_s int_range_t;

/* Prototypes */
int_range_t *irange(int start, int end);



//irange.c
#include "irange.h"

typedef struct int_range_s {
int length;
int nums[];
} int_range_t;

/*
* Function : irange
* Arguments: int start - initial int, int end - final int
* (if start > end the range will be in descending order)
* Returns : int_range_t or NULL
* Notes : The caller has to free the allocated memory
*/
int_range_t *irange(int start, int end)
{
bool reverse = (end < start);
int size = (reverse ? start - end : end - start) + 1;
size_t mem = sizeof(int_range_t) + size * sizeof(int);
int_range_t *range = malloc(mem);

if (range == NULL) {
return NULL;
}

range->length = size;

for (int i = 0; i < size; i += 1) {
range->nums[i] = reverse ? start - i : start + i;
}

return range;
}



Now, when I try something like that:

gcc -Wall -g -std=c99 -o main main.c arange.c irange.c -lm


I get such errors:

main.c: In function ‘main’:
main.c:14:34: error: dereferencing pointer to incomplete type
for (int i = 0; i < int_range->length; i++) {
^
main.c:15:31: error: dereferencing pointer to incomplete type
printf("%d", int_range->nums[i]);
^
main.c:20:35: error: dereferencing pointer to incomplete type
for (int i = 0; i < char_range->length; i++) {
^
main.c:21:32: error: dereferencing pointer to incomplete type
printf("%c", char_range->chars[i]);
^


It seems like something has gone wrong with the linking but I must say I'm lost... Should I move entire typedef struct definitions into header files?

Edit: Yeah, that solved it. And now I know that my program segfaults on char_range->length and I have no idea why
Time is precious. Waste it wisely.
Ropid
Profile Joined March 2009
Germany3557 Posts
May 07 2016 15:29 GMT
#14526
Yes, the struct has to be in the header file. I think about translating the "->" and "." into memory offsets in the machine code, this part of the job is done by the compiler, not the linker, so the compiler has to know about the concrete sizes of elements inside structs. It then needs the definition of the struct inside each file it compiles, so it needs to be in the header file that you're including everywhere you need a type.
"My goal is to replace my soul with coffee and become immortal."
Hhanh00
Profile Joined May 2016
34 Posts
May 07 2016 16:24 GMT
#14527
Your issue is with conversion from char to int. You use


int val = input - '0';


But in C, chars are already integers from 0 to 255, so use them as such (don't substract '0').

Sometimes you'll see that code, but it has a different purpose. It converts the digits from 0 to 9 from ASCII code to ordinal.

Actually, 'A' is the same as 65 and you could write


if ((val >= 'A' && val <= 'Z') || (val >= 'a' && val <= 'z')) {


or better yet, use isalpha(input) from ctype.h

Wrath
Profile Blog Joined July 2014
3174 Posts
May 07 2016 18:46 GMT
#14528
Google down?
Acrofales
Profile Joined August 2010
Spain17971 Posts
May 07 2016 18:50 GMT
#14529
On May 08 2016 03:46 Wrath wrote:
Google down?

no
Wrath
Profile Blog Joined July 2014
3174 Posts
May 07 2016 19:06 GMT
#14530
Damn you were too fast. It is working now again. Minutes ago I could not load anything, gmail / google / translator. All were giving errors. Not sure what was the issue.
Blitzkrieg0
Profile Blog Joined August 2010
United States13132 Posts
May 07 2016 23:05 GMT
#14531
Does anyone know a good book or program to practice troubleshooting with gdb? Preferably C++ oriented, but that doesn't really matter.
I'll always be your shadow and veil your eyes from states of ain soph aur.
Manit0u
Profile Blog Joined August 2004
Poland17243 Posts
May 08 2016 00:00 GMT
#14532
On May 08 2016 01:24 Hhanh00 wrote:
Your issue is with conversion from char to int. You use


int val = input - '0';


But in C, chars are already integers from 0 to 255, so use them as such (don't substract '0').

Sometimes you'll see that code, but it has a different purpose. It converts the digits from 0 to 9 from ASCII code to ordinal.

Actually, 'A' is the same as 65 and you could write


if ((val >= 'A' && val <= 'Z') || (val >= 'a' && val <= 'z')) {


or better yet, use isalpha(input) from ctype.h



Great. Thanks for that. But can I also do regular math on chars ('z' - 'a' for example)? Will the return type be integer?

I'll have to try it out as that would simplify the code for me greatly.
Time is precious. Waste it wisely.
Cyx.
Profile Joined November 2010
Canada806 Posts
Last Edited: 2016-05-08 17:28:19
May 08 2016 00:06 GMT
#14533
On May 08 2016 09:00 Manit0u wrote:
Great. Thanks for that. But can I also do regular math on chars ('z' - 'a' for example)? Will the return type be integer?

I'll have to try it out as that would simplify the code for me greatly.

Yeah you can, the type will be char but `int x = 'z' - 'a'` will compile just fine and work as you expect it to so it's a pretty academic point.

edit: I'm wrong, see below
Biolunar
Profile Joined February 2012
Germany224 Posts
May 08 2016 07:21 GMT
#14534
On May 08 2016 09:06 Cyx. wrote:
Show nested quote +
On May 08 2016 09:00 Manit0u wrote:
Great. Thanks for that. But can I also do regular math on chars ('z' - 'a' for example)? Will the return type be integer?

I'll have to try it out as that would simplify the code for me greatly.

Yeah you can, the type will be char but `int x = 'z' - 'a'` will compile just fine and work as you expect it to so it's a pretty academic point.

No. The type of 'a' - 'z' is int. What happens here is called integer promotion.
What is best? To crush the Zerg, see them driven before you, and hear the lamentations of the Protoss.
Cyx.
Profile Joined November 2010
Canada806 Posts
May 08 2016 17:28 GMT
#14535
On May 08 2016 16:21 Biolunar wrote:
No. The type of 'a' - 'z' is int. What happens here is called integer promotion.

I stand corrected, I read the relevant sections of the standard and you're definitely right.
waffelz
Profile Blog Joined June 2012
Germany711 Posts
Last Edited: 2016-05-08 22:12:35
May 08 2016 22:11 GMT
#14536
On May 01 2016 03:10 amazingxkcd wrote:
Show nested quote +
On May 01 2016 02:21 Artesimo wrote:
I am forced to use netbeans for a number of reasons. I am just baffled how "incredible" it is, given the fact that we are forced to work with it in some lectures. Right now I am just coding with gedit and giggle like a retard when I copy my code into netbeans and it just compiles even though it marks almost everything as wrong. It is better then the other way around


netbeans is fine but you have to spend time to set the IDE up right.


Even though I am late to the party: just no. Maybe it is somewhat fine for java, but for C++ Netbeans is a piece of shit that should have died a long time ago, yet it annoyingly finds its way onto pretty much any lab-computer in universities that runs a Unix system.
I can't tell you how much of my time this thing wasted by either giving completely misleading warnings/error-messages or straight up messing shit up on his own. It believes c++11 is highly experimental and therefore you should always default to c++98, it is slow as hell, every default theme is probably the best example for poor visibility, it likes to waste your time and to break itself. Last semester I had to fix some linker settings multiple times and it somehow forgot the correct path to some of the standard-includes 2 times without me every changing anything that could have caused that. The only good thing I can say about Netbeans is the quick “fix imports”-function and the refactor-function and both you can get as an extension for pretty much any IDE that is somewhat up to date.
By this time, whenever some assignment features programming on UNIX, I am praying that we are allowed to use our own machines instead of the lab because if notepad++ would feature a compiler, it would make a better IDE.

Netbeans is a crime against humanity.
RIP "The big travis CS degree thread", taken from us too soon | Honourable forum princess, defended by Rebs-approved white knights
Acrofales
Profile Joined August 2010
Spain17971 Posts
Last Edited: 2016-05-09 00:10:54
May 09 2016 00:08 GMT
#14537
Even for java, I prefer both intellij and eclipse. That said, eclipse's c support is absolutely awful. In fact, eclipse for anything non-java is a horrible experience, whereas pycharm and webstorm are both amazing. How is CLion?
Manit0u
Profile Blog Joined August 2004
Poland17243 Posts
Last Edited: 2016-05-09 01:29:43
May 09 2016 01:28 GMT
#14538
On May 09 2016 09:08 Acrofales wrote:
Even for java, I prefer both intellij and eclipse. That said, eclipse's c support is absolutely awful. In fact, eclipse for anything non-java is a horrible experience, whereas pycharm and webstorm are both amazing. How is CLion?


You can trial it yourself you know

But seriously, I have yet to find Jetbrains product that wouldn't deliver.

And to anyone saying that Netbeans is good - have you ever tried to turn on whitespace visibility in it? Or trimming trailing whitespace for that matter?
Time is precious. Waste it wisely.
Hhanh00
Profile Joined May 2016
34 Posts
May 09 2016 02:30 GMT
#14539
On Windows, Dev Studio is the best. On MacOS, it's XCode obviously. On Linux, none of them are as good.
Shield
Profile Blog Joined August 2009
Bulgaria4824 Posts
May 09 2016 19:04 GMT
#14540
On May 09 2016 11:30 Hhanh00 wrote:
On Windows, Dev Studio is the best. On MacOS, it's XCode obviously. On Linux, none of them are as good.


When you say Dev Studio do you mean Visual Studio? No one refers to Dev Studio at work..
Prev 1 725 726 727 728 729 1031 Next
Please log in or register to reply.
Live Events Refresh
BSL: ProLeague
18:00
Grand Finals - bo9
Dewalt vs Bonyth
ZZZero.O615
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Livibee 92
ProTech81
StarCraft: Brood War
ZZZero.O 615
Terrorterran 43
League of Legends
Grubby4460
Dendi1322
Counter-Strike
fl0m1811
Super Smash Bros
Mew2King204
Chillindude77
Westballz49
Heroes of the Storm
Khaldor803
Liquid`Hasu661
Other Games
summit1g4866
FrodaN2916
tarik_tv790
mouzStarbuck327
Pyrionflax208
ViBE124
elazer94
Organizations
Other Games
gamesdonequick44472
EGCTV1715
BasetradeTV47
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 18 non-featured ]
StarCraft 2
• musti20045 62
• Adnapsc2 25
• Kozan
• Migwel
• AfreecaTV YouTube
• sooper7s
• intothetv
• IndyKCrew
• LaughNgamezSOOP
StarCraft: Brood War
• 3DClanTV 101
• blackmanpl 6
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• Ler140
League of Legends
• masondota2734
Other Games
• imaqtpie2305
• Shiphtur360
Upcoming Events
Wardi Open
13h 19m
Replay Cast
1d 2h
Sparkling Tuna Cup
1d 12h
WardiTV European League
1d 18h
MaNa vs sebesdes
Mixu vs Fjant
ByuN vs HeRoMaRinE
ShoWTimE vs goblin
Gerald vs Babymarine
Krystianer vs YoungYakov
PiGosaur Monday
2 days
The PondCast
2 days
WardiTV European League
2 days
Jumy vs NightPhoenix
Percival vs Nicoract
ArT vs HiGhDrA
MaxPax vs Harstem
Scarlett vs Shameless
SKillous vs uThermal
Replay Cast
3 days
RSL Revival
3 days
ByuN vs SHIN
Clem vs Reynor
Replay Cast
4 days
[ Show More ]
RSL Revival
4 days
Classic vs Cure
FEL
4 days
RSL Revival
5 days
FEL
5 days
FEL
5 days
Sparkling Tuna Cup
6 days
RSL Revival
6 days
FEL
6 days
Liquipedia Results

Completed

BSL 2v2 Season 3
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL Season 20
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
CSL Xiamen Invitational
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.