• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 03:44
CEST 09:44
KST 16:44
  • 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
RSL Season 1 - Final Week6[ASL19] Finals Recap: Standing Tall11HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7Weekly Cups (June 30 - July 6): Classic Doubles7[BSL20] Non-Korean Championship 4x BSL + 4x China10Flash Announces Hiatus From ASL76
StarCraft 2
General
RSL Revival patreon money discussion thread The GOAT ranking of GOAT rankings Weekly Cups (June 30 - July 6): Classic Doubles Server Blocker RSL Season 1 - Final Week
Tourneys
RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event $5,100+ SEL Season 2 Championship (SC: Evo) $25,000 Streamerzone StarCraft Pro Series announced Sparkling Tuna Cup - Weekly Open Tournament
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
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
[ASL19] Finals Recap: Standing Tall BGH Auto Balance -> http://bghmmr.eu/ Flash Announces Hiatus From ASL BW General Discussion A cwal.gg Extension - Easily keep track of anyone
Tourneys
2025 ACS Season 2 Qualifier [Megathread] Daily Proleagues Small VOD Thread 2.0 Last Minute Live-Report Thread Resource!
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile CCLP - Command & Conquer League Project The PlayStation 5 Nintendo Switch Thread
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 Things Aren’t Peaceful in Palestine The Accidental Video Game Porn Archive Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\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
The Automated Ban List
Blogs
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 638 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
Poland17247 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
Spain17975 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
Poland17247 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
Spain17975 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
Poland17247 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
Next event in 2h 16m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nina 259
StarCraft: Brood War
Sea 13412
PianO 1803
Larva 595
Leta 529
Shinee 84
Sacsri 19
Noble 16
Stormgate
NightEnD7
Dota 2
ODPixel566
XcaliburYe125
League of Legends
JimRising 703
Counter-Strike
Stewie2K1412
Super Smash Bros
Westballz15
Heroes of the Storm
Khaldor250
Other Games
SortOf117
Organizations
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 13 non-featured ]
StarCraft 2
• Berry_CruncH352
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2124
League of Legends
• Jankos2488
Upcoming Events
Sparkling Tuna Cup
2h 16m
RSL Revival
2h 16m
Classic vs Clem
FEL
7h 16m
Elazer vs Spirit
Gerald vs MaNa
BSL20 Non-Korean Champi…
10h 16m
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Wardi Open
1d 3h
Replay Cast
2 days
WardiTV European League
2 days
PiGosaur Monday
2 days
uThermal 2v2 Circuit
3 days
Replay Cast
3 days
[ Show More ]
The PondCast
4 days
Replay Cast
4 days
Epic.LAN
5 days
CranKy Ducklings
6 days
Epic.LAN
6 days
BSL20 Non-Korean Champi…
6 days
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Liquipedia Results

Completed

KCM Race Survival 2025 Season 2
HSC XXVII
NC Random Cup

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
2025 ACS Season 2: Qualifier
BSL20 Non-Korean Championship
CSLPRO Last Chance 2025
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

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
2025 ACS Season 2
CSLPRO Chat StarLAN 3
BSL Season 21
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
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.