Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Locked thread
Corla Plankun
May 8, 2007

improve the lives of everyone

Blinkz0rz posted:

cases in which you need recursion:

  • interview questions

ftfy

Adbot
ADBOT LOVES YOU

Xarn
Jun 26, 2015

fleshweasel posted:

I'm representing the bitmap with a std::vector<std::vector<int>> which could be bad. I pass a pointer to the vector in with the thread start arguments for each thread as well as the index into the outer vector that the thread should start inserting into the inner vector. I ran it with Instruments on macOS which made it look like half of my time is being spent in cabs though (absolute value of a complex number).

I feel like there's probably something really stupid going on causing threads to block each other or something. Running it with 2 threads is actually slower than my single threaded implementation without std::thread.

posting code because why the gently caress not

code:
#include <iostream>
#include <complex>
#include <vector>
#include <chrono>
#include <thread>
#include <SDL/SDL.h>
#include "sdl_helpers.h"
#include "mandelbrot_common.h"

struct thread_params
{
	std::vector<std::vector<int>> *set;
	int min_x;
	int max_x;
	int width;
	int height;
};

void mandelbrot_thread(thread_params *p)
{
	for (int i = p->min_x; i < p->max_x; i++) {
		std::vector<int> column(p->height);
		for (int j = 0; j < p->height; j++) {
			double x_norm = (double)i / p->width;
			double y_norm = (double)j / p->height;
			int iters = mandelbrot(std::complex<double>(x_norm, y_norm));
			column[j] = iters;
		}
		(*p->set)[i] = column;
	}
}

std::vector<std::vector<int>> mandelbrot_set(int width, int height)
{
	constexpr int num_threads = 1024;
	std::cout << "Number of threads: " << num_threads << "\n";

	auto set = new std::vector<std::vector<int>>(width);
	std::vector<std::thread*> threads;

	int slice = width / num_threads;
	for (int i = 0; i < num_threads; i++) {
		struct thread_params *p = new struct thread_params;
		p->set = set;
		p->min_x = slice * i;
		p->max_x = slice * (i + 1);
		p->width = width;
		p->height = height;

		std::thread *t = new std::thread(mandelbrot_thread, p);
		threads.push_back(t);
	}
	for (std::thread *t : threads) {
		t->join();
		delete t;
	}

	return *set;
}

int main(int argc, char **argv)
{
	std::chrono::system_clock clock;

	auto before = clock.now();
	auto set = mandelbrot_set(MAX_X, MAX_Y);
	auto after = clock.now();
	std::chrono::duration<double> diff = after - before;
	render_mandelbrot(set, diff.count());

	return 0;
}

Ill try to look through the threading later, but first I gotta go over your C++. :v:

First of all, C++ works with just thread_params, no need to specify its a struct.
Second, the "new"s are pointless -> this should work just as well
C++ code:
#include <iostream>
#include <complex>
#include <vector>
#include <chrono>
#include <thread>
#include <SDL/SDL.h>
#include "sdl_helpers.h"
#include "mandelbrot_common.h"

struct thread_params
{
	std::vector<std::vector<int>> *set;
	int min_x;
	int max_x;
	int width;
	int height;
};

void mandelbrot_thread(thread_params p)
{
	for (int i = p.min_x; i < p.max_x; i++) {
		std::vector<int> column(p.height);
		for (int j = 0; j < p.height; j++) {
			double x_norm = (double)i / p.width;
			double y_norm = (double)j / p.height;
			int iters = mandelbrot(std::complex<double>(x_norm, y_norm));
			column[j] = iters;
		}
        // You can move the colum outside, in this case it doesn't do it automatically as it isn't actually returned.
		(*p->set)[i] = std::move(column);
	}
}

std::vector<std::vector<int>> mandelbrot_set(int width, int height)
{
	constexpr int num_threads = 1024;
	std::cout << "Number of threads: " << num_threads << "\n";

	auto set = std::vector<std::vector<int>>(width);
	std::vector<std::thread> threads;

	int slice = width / num_threads;
	for (int i = 0; i < num_threads; i++) {
		thread_params params;
        // Alternatively: thread_params params{&set, slice * i, slice * (i + 1), width, height};
		p.set = &set;
		p.min_x = slice * i;
		p.max_x = slice * (i + 1);
		p.width = width;
		p.height = height;

        // Alternatively, thread.emplace_back(mandelbrot_thread, params);
        threads.push_back(std::thread(mandelbrot_thread, params);
	}
	for (std::thread& t : threads) {
		t.join();
	}

    // You were missing a delete here, meaning memory leak
	return set;
}

int main(int argc, char **argv)
{
	std::chrono::system_clock clock;

	auto before = clock.now();
	auto set = mandelbrot_set(MAX_X, MAX_Y);
	auto after = clock.now();
	std::chrono::duration<double> diff = after - before;
	render_mandelbrot(set, diff.count());

	return 0;
}

Deep Dish Fuckfest
Sep 6, 2006

Advanced
Computer Touching


Toilet Rascal

Blinkz0rz posted:

cases in which you need recursion:

  • traversal
  • mathy poo poo
  • ????
  • teaching cs 101 and pranking the gently caress out of freshmen by showing them the least efficient way of computing fibonacci numbers (and never telling them it's garbage)

Soricidus
Oct 21, 2010
freedom-hating statist shill

Blinkz0rz posted:

cases in which you need recursion:

  • traversal
  • mathy poo poo
  • ????

parsing, if you do it the easy way

Luigi Thirty
Apr 30, 2006

Emergency confection port.

we did it without any help from the operating system



:toot:

Xarn
Jun 26, 2015

Luigi Thirty posted:

we did it without any help from the operating system



:toot:

Sweet.

MononcQc
May 29, 2007

recursion is also cool when you represent state machines as series of function calls; a repeated state just needs to call itself again, and if you get tail call optimization you can implement long-lived state machines that way very easy.

lets you do poo poo like:

code:
wait_any_key() ->
    get_line("To Start, Press Any Key.\n> ")
    first_core_temperature_check()

first_core_temperature_check() ->
    case option("Check core temperature?") of
        yes -> show_core_temperature();
        no -> noop()
    end
    first_gas_vent()

first_gas_vent() ->
    case option("Vent radioactive gas?") of
        yes -> show_blow_crops_away()
        no -> show_venting_prevents_explosions()
    end
    wait_for_command()

...
which can end up being pretty sweet.

theodop
Dec 30, 2005

rock solid, heart touching

LeftistMuslimObama posted:

no. we make our own ide in-house that has features for all our extra architecture on top of mumps

jfc dude

carry on then
Jul 10, 2010

by VideoGames

(and can't post for 10 years!)

theodop posted:

jfc dude

not invented here syndrome is great

theodop
Dec 30, 2005

rock solid, heart touching
the hilarious thing is that it is 2 layers of "not invented here" syndrome.

InterSystems are Not Invented Here: The Company

They have invented:

1. like 6 languages
2. their own SQL variant
3. their own ASP clone
4. their own WebForms clone / bizarre MVVM clusterfuck
5. their own standard library
6. their own terrible IDE
7. several web server implementations

and this is just from me thinking of the things I've used in like the last week

then Epic is looking at this house of cards and thinking "looks great, but what it really needs is another layer on top"

Sapozhnik
Jan 2, 2005

Nap Ghost
oh god there has to be a way to do this generics thing in java without blowing the lid off a c++-level cauldron of type signature nightmares

redleader
Aug 18, 2005

Engage according to operational parameters
i used recursion once, to merge two xml documents. the code was, needless to say, very bad. took me a while to get it right too

i am a v. terrible programmer

Fergus Mac Roich
Nov 5, 2008

Soiled Meat

redleader posted:

i used recursion once, to merge two xml documents. the code was, needless to say, very bad. took me a while to get it right too

i am a v. terrible programmer

read SICP it's fun

& the lectures from the 80s are on YouTube

Blinkz0rz
May 27, 2001

MY CONTEMPT FOR MY OWN EMPLOYEES IS ONLY MATCHED BY MY LOVE FOR TOM BRADY'S SWEATY MAGA BALLS
i used recursion recently to walk up a tree, doing the same operation on a node until it reaches a terminator. p much tailor made for recursion but basically the only thing i've ever used it for except fibonacci sequence interview questions

FamDav
Mar 29, 2008

Sapozhnik posted:

oh god there has to be a way to do this generics thing in java without blowing the lid off a c++-level cauldron of type signature nightmares

what do you want to do

Sapozhnik
Jan 2, 2005

Nap Ghost
writing a rest server for my hobby project

surprisingly hard to design something good in this space although actually i feel like i've come up with some good designs, i'll probably extract the framework code and upload it to a github repo for ppl to point & laugh at

FamDav
Mar 29, 2008

Sapozhnik posted:

writing a rest server for my hobby project

surprisingly hard to design something good in this space although actually i feel like i've come up with some good designs, i'll probably extract the framework code and upload it to a github repo for ppl to point & laugh at

annotations and reflection. here's a hello world for dropwizard https://github.com/skylinerhq/hello-dropwizard

Sapozhnik
Jan 2, 2005

Nap Ghost
dropwizard is poo poo, it is aimed at the sort of people who would be happier writing python

e: not that there's necessarily anything wrong with python, i just don't see the point of writing python in java as opposed to writing python in python

jony neuemonic
Nov 13, 2009

Sapozhnik posted:

dropwizard is poo poo, it is aimed at the sort of people who would be happier writing python

e: not that there's necessarily anything wrong with python, i just don't see the point of writing python in java as opposed to writing python in python

what don't you like about it? it always looked pretty decent, but i'm mostly a c# guy.

fart simpson
Jul 2, 2005

DEATH TO AMERICA
:xickos:

i used recursion literally all the time in haskell and elm

kitten emergency
Jan 13, 2008

get meow this wack-ass crystal prison
is programming games at all interesting from a hobby project perspective

I've never used unity or w/e and I have the artistic skills of a drunken bull moose

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
designing games is fun, and programming a game you've designed is a cool project

programming something that vaguely looks like a game without putting any design effort into it is pretty bad though. unless you're making an implementation of a game that someone else put the design effort into.

Asymmetrikon
Oct 30, 2009

I believe you're a big dork!

fart simpson posted:

i used recursion literally all the time in haskell and elm

same, but only through hofs like fold and never explicitly (or as little explicitly as possible)

kitten emergency
Jan 13, 2008

get meow this wack-ass crystal prison

Jabor posted:

designing games is fun, and programming a game you've designed is a cool project

programming something that vaguely looks like a game without putting any design effort into it is pretty bad though. unless you're making an implementation of a game that someone else put the design effort into.

hm alright

The MUMPSorceress
Jan 6, 2012


^SHTPSTS

Gary’s Answer
ok, so i guess im wrong about that. thanks for the lies compilers teacher.

i guess i just find all the divide-and-conquer algos to be way easier to picture mentally with recursion, but i was never taught the iterative versions so everything i know about them is my own bodged-together understanding.

how does the iterative version of something like, say, merge sort work? you just make to subarrays, push them onto a stack, then pop the stack and repeat? i feel like i'd gently caress that up my first couple of tries but i should probably implement some toy algos like that just to get a feel. i hate that my job has very little to do with algorithms.

Bloody
Mar 3, 2013

easiest approach is generally to replace the implicit stack that you'd build with recursive calls with an explicit stack which can be stored somewhere other than the call stack

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
mergesort in particular has predetermined partitions so you only really need to track where you are in the process, you don't need to keep a stack of which partitions have been sorted or anything.

but yeah in general for things like tree algorithms you essentially replace the recursive calls with "add this to the list of things to do" and then put it all in a loop that starts with "get the next thing to do"

redleader
Aug 18, 2005

Engage according to operational parameters
i should probably learn some of those basic cs algorithms lol

The MUMPSorceress
Jan 6, 2012


^SHTPSTS

Gary’s Answer

Jabor posted:

mergesort in particular has predetermined partitions so you only really need to track where you are in the process, you don't need to keep a stack of which partitions have been sorted or anything.

but yeah in general for things like tree algorithms you essentially replace the recursive calls with "add this to the list of things to do" and then put it all in a loop that starts with "get the next thing to do"

neat. and all the sorting algos get mixed up in my head because sorting is trivial in my lang, so i just remember that they're mostly "break array in half, do thing".

i remember when i was a kid learning programming out of books and whatever i would always use linked lists for everything even if i had to roll my own because i was scared shitless of doing math on arrays, lol. my lovely text adventures were so god damned slow.

Luigi Thirty
Apr 30, 2006

Emergency confection port.



hmmmm trying to figure out how to wrap my tilemap around so I don't get the jumping when we run out of room to draw

one screen is 14 rows of 20 tiles and I've got a bitplane big enough to store 28 rows of tiles. at the start of a frame I can set the graphics pointer to read at any point in the bitplane. the scrolling is just moving the pointer up by one scanline each frame.

I think what I need to do is draw each new row of tiles twice, once on each half of the screen so 14 rows apart. then when I reach the end of the bitplane I can reset the pointer to the bottom half of the bitplane and keep drawing as if nothing has happened

(the colors are wrong because I don't have masking set up right)

Sapozhnik
Jan 2, 2005

Nap Ghost

redleader posted:

i should probably learn some of those basic cs algorithms lol

ehh

the only times you'll ever find yourself actually implementing any of them is in a programming interview, which should tell you something.

it is very rare that you'll need to care about what exact kind of sort your language's standard library sort is performing.

(heap sort is the best general purpose sort though, for the record)

Bloody
Mar 3, 2013

interviews, like cs programs, focus on the least relevant issues (like algorithms) instead of vastly more important but difficult to quantify or directly address skills like architecture, design, debugging, learning new technologies or systems, dealing with people, googling for answers,

The MUMPSorceress
Jan 6, 2012


^SHTPSTS

Gary’s Answer

Bloody posted:

interviews, like cs programs, focus on the least relevant issues (like algorithms) instead of vastly more important but difficult to quantify or directly address skills like architecture, design, debugging, learning new technologies or systems, dealing with people, googling for answers,

is dick size comparison ever relevant in these interviews?

redleader
Aug 18, 2005

Engage according to operational parameters
it kinda seems that "basic cs knowledge" would be something of a prerequisite for any interesting/challenging/novel work

but then i remember where i live and the dearth of any jobs like that and go back to my usual state of ennui

Fergus Mac Roich
Nov 5, 2008

Soiled Meat

Sapozhnik posted:

(heap sort is the best general purpose sort though, for the record)

assuming you're not joking, why do you say that? i thought timsort was the most common standard library generic sort.

the talent deficit
Dec 20, 2003

self-deprecation is a very british trait, and problems can arise when the british attempt to do so with a foreign culture





i only know how to do things recursively. i write c using goto

Luigi Thirty
Apr 30, 2006

Emergency confection port.

LeftistMuslimObama posted:

is dick size comparison ever relevant in these interviews?

dick presence usually is unfortunately

Sapozhnik
Jan 2, 2005

Nap Ghost

Fergus Mac Roich posted:

assuming you're not joking, why do you say that? i thought timsort was the most common standard library generic sort.

I mean if you're no-poo poo writing a standard library then go with whatever insanely complicated hybrid adaptive sorting algorithm you can, I suppose.

if you just want something O(n log n), period, and not "oh well the worst case is O(n^2) but really it's more like O(n log n) in practice faaaart" with no auxiliary space requirements then that's literally just heap sort and nothing else afaik. and it's still fairly simple.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
you can do in-place mergesort if you're clever about it

Adbot
ADBOT LOVES YOU

Fergus Mac Roich
Nov 5, 2008

Soiled Meat

Sapozhnik posted:

I mean if you're no-poo poo writing a standard library then go with whatever insanely complicated hybrid adaptive sorting algorithm you can, I suppose.

if you just want something O(n log n), period, and not "oh well the worst case is O(n^2) but really it's more like O(n log n) in practice faaaart" with no auxiliary space requirements then that's literally just heap sort and nothing else afaik. and it's still fairly simple.

point taken about the ease of implementation. i was considering that perhaps stability might be a more common requirement than no extra space, but if we're already in an environment where some kind of Arrays.Sort() method isn't available, maybe memory is that big of an issue.

Jabor posted:

you can do in-place mergesort if you're clever about it

http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html wow it's stable too, that's neat.

  • Locked thread