Blog

// linebreak.cpp — 같은 문단, 다른 줄 바꿈 알고리즘(전략): 탐욕 vs 균형(DP)
#include <climits>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <vector>

using Words = std::vector<std::string>;
using Lines = std::vector<std::string>;

struct LineBreaker {                                         // Strategy
	virtual ~LineBreaker() = default;
	virtual Lines wrap(const Words &w, std::size_t width) const = 0;
	virtual const char *name() const = 0;
};

struct Greedy : LineBreaker {                                // 들어갈 수 있는 만큼 채운다
	const char *name() const override { return "greedy"; }
	Lines wrap(const Words &w, std::size_t width) const override
	{
		Lines out{""};
		for (const auto &x : w) {
			if (!out.back().empty() && out.back().size() + 1 + x.size() > width)
				out.push_back("");
			out.back() += (out.back().empty() ? "" : " ") + x;
		}
		return out;
	}
};

struct Balanced : LineBreaker {                              // 줄 끝 여백 제곱합 최소(마지막 줄 제외)
	const char *name() const override { return "balanced"; }
	Lines wrap(const Words &w, std::size_t width) const override
	{
		std::size_t n = w.size();
		std::vector<long> cost(n + 1, LONG_MAX);
		std::vector<std::size_t> brk(n + 1);
		cost[n] = 0;
		for (std::size_t i = n; i-- > 0;) {
			std::size_t len = 0;
			for (std::size_t j = i; j < n; ++j) {
				len += w[j].size() + (j > i);
				if (len > width) break;
				long slack = long(width - len);
				long c = (j + 1 == n ? 0 : slack * slack) + cost[j + 1];
				if (c < cost[i]) { cost[i] = c; brk[i] = j + 1; }
			}
		}
		Lines out;
		for (std::size_t i = 0; i < n; i = brk[i]) {
			std::string line;
			for (std::size_t j = i; j < brk[i]; ++j)
				line += (j > i ? " " : "") + w[j];
			out.push_back(line);
		}
		return out;
	}
};

class Paragraph {                                            // Context
public:
	Paragraph(const std::string &text, const LineBreaker &b) : breaker_(&b)
	{ std::istringstream in(text); for (std::string x; in >> x;) words_.push_back(x); }
	void setBreaker(const LineBreaker &b) { breaker_ = &b; }
	void render(std::size_t width) const
	{
		long raggedness = 0;
		auto lines = breaker_->wrap(words_, width);
		std::cout << breaker_->name() << ":\n";
		for (std::size_t i = 0; i < lines.size(); ++i) {
			std::cout << "  |" << lines[i] << std::string(width - lines[i].size(), ' ') << "|\n";
			if (i + 1 < lines.size()) raggedness += long(width - lines[i].size()) * long(width - lines[i].size());
		}
		std::cout << "  raggedness=" << raggedness << '\n';
	}
private:
	const LineBreaker *breaker_;
	Words words_;
};

int main()
{
	Greedy greedy;
	Balanced balanced;
	Paragraph p("aaa bb cc ddddd", greedy);
	p.render(6);
	p.setBreaker(balanced);                                  // 실행 중 전략 교체
	p.render(6);

	Paragraph q("Strategy lets the algorithm vary independently from clients that use it", greedy);
	q.render(16);
	q.setBreaker(balanced);
	q.render(16);
}

// bench.cpp — 전략을 넘기는 세 방식의 호출 비용: 가상 함수, std::function, 템플릿
// 메모리 대역폭에 가려지지 않도록 루프 인덱스만 넘기는 계산 위주 루프로 잰다
#include <chrono>
#include <cstdint>
#include <functional>
#include <iostream>

constexpr std::uint64_t N = 200'000'000;

struct Op { virtual ~Op() = default; virtual std::uint64_t apply(std::uint64_t x) const = 0; };
struct Mix : Op { std::uint64_t apply(std::uint64_t x) const override { return x * 0x9E3779B97F4A7C15ull + 1; } };

// noipa: 컴파일러가 함수 간 분석으로 호출을 합치거나 상수로 접지 못하게 한다
__attribute__((noipa)) std::uint64_t run_virtual(const Op &op)
{ std::uint64_t s = 0; for (std::uint64_t i = 0; i < N; ++i) s += op.apply(i); return s; }

__attribute__((noipa)) std::uint64_t run_function(const std::function<std::uint64_t(std::uint64_t)> &f)
{ std::uint64_t s = 0; for (std::uint64_t i = 0; i < N; ++i) s += f(i); return s; }

template <class F>
__attribute__((noipa)) std::uint64_t run_template(F f)
{ std::uint64_t s = 0; for (std::uint64_t i = 0; i < N; ++i) s += f(i); return s; }

template <class F>
void measure(const char *name, F body)
{
	auto t0 = std::chrono::steady_clock::now();
	std::uint64_t r = body();
	auto ms = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count();
	std::cout << name << ms << " ms  (" << ms * 1e6 / N << " ns/call, checksum " << (r & 0xffff) << ")\n";
}

int main()
{
	Mix mix;
	const Op &op = mix;
	auto lam = [](std::uint64_t x) { return x * 0x9E3779B97F4A7C15ull + 1; };
	std::function<std::uint64_t(std::uint64_t)> fn = lam;

	measure("virtual       : ", [&] { return run_virtual(op); });
	measure("std::function : ", [&] { return run_function(fn); });
	measure("template      : ", [&] { return run_template(lam); });
}

/* hash_strategy.c — C 전략: 해시 테이블에 해시 함수를 함수 포인터로 꽂는다 */
#include <stdio.h>
#include <string.h>

#define NBUCKET 1024
#define NKEY    4096

typedef unsigned (*hash_fn)(const char *s);

static unsigned hash_sum(const char *s)            /* 문자 코드 합: 흔한 나쁜 예 */
{
	unsigned h = 0;
	while (*s)
		h += (unsigned char)*s++;
	return h;
}

static unsigned hash_djb2(const char *s)
{
	unsigned h = 5381;
	while (*s)
		h = h * 33 + (unsigned char)*s++;
	return h;
}

static unsigned hash_fnv1a(const char *s)
{
	unsigned h = 2166136261u;
	while (*s)
		h = (h ^ (unsigned char)*s++) * 16777619u;
	return h;
}

struct table {                                     /* Context */
	hash_fn hash;                                  /* Strategy */
	int count[NBUCKET];
};

static void table_stats(struct table *t, const char *name)
{
	char key[32];
	int used = 0, longest = 0;

	memset(t->count, 0, sizeof(t->count));
	for (int i = 0; i < NKEY; i++) {
		snprintf(key, sizeof(key), "user%04d", i);
		t->count[t->hash(key) % NBUCKET]++;
	}
	for (int b = 0; b < NBUCKET; b++) {
		used += t->count[b] > 0;
		if (t->count[b] > longest)
			longest = t->count[b];
	}
	printf("%-6s used buckets=%4d/%d  longest chain=%4d\n", name, used, NBUCKET, longest);
}

int main(void)
{
	struct { const char *name; hash_fn fn; } strategies[] = {
		{ "sum", hash_sum }, { "djb2", hash_djb2 }, { "fnv1a", hash_fnv1a },
	};
	struct table t;

	for (size_t i = 0; i < sizeof(strategies) / sizeof(strategies[0]); i++) {
		t.hash = strategies[i].fn;                 /* 실행 중 전략 교체 */
		table_stats(&t, strategies[i].name);
	}
	return 0;
}